import java.util.*;

class TencentSelectedSolution {
    // 2. 两数相加
    // 给你两个 非空 的链表，表示两个非负的整数。
    // 它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
    // 请你将两个数相加，并以相同形式返回一个表示和的链表。
    // 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
    // 提示：
    // 每个链表中的节点数在范围 [1, 100] 内
    // 0 <= Node.val <= 9
    // 题目数据保证列表表示的数字不含前导零

    // 方法一：（自己写的）迭代（遍历链表）-时间复杂度：O(n)，空间复杂度：O(1)
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(-1);
        ListNode curr = dummyHead;
        int adder = 0;
        while (l1 != null || l2 != null || adder != 0) {
            int l1Val = 0;
            if (l1 != null) {
                l1Val = l1.val;
                l1 = l1.next;
            }
            int l2Val = 0;
            if (l2 != null) {
                l2Val = l2.val;
                l2 = l2.next;
            }
            int sum = l1Val + l2Val + adder;
            adder = sum / 10;
            int val = sum % 10;
            curr.next = new ListNode(val);
            curr = curr.next;
        }
        return dummyHead.next;
    }

    // 4. 寻找两个正序数组的中位数
    // 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
    // 请你找出并返回这两个正序数组的 中位数 。
    // 算法的时间复杂度应该为 O(log (m+n)) 。
    // 提示：
    // nums1.length == m
    // nums2.length == n
    // 0 <= m <= 1000
    // 0 <= n <= 1000
    // 1 <= m + n <= 2000
    // -106 <= nums1[i], nums2[i] <= 106
    // 如果对时间复杂度的要求有 log，通常都需要用到二分查找

    // 方法一：二分查找-时间复杂度：O(log(m+n))，空间复杂度：O(1)
    // 这道题可以转化成寻找两个有序数组中的第 k 小的数，其中 k 为 (m+n)/2 或 (m+n)/2+1。
    // 如果 A[k/2−1]<B[k/2−1]，则比A[k/2−1] 小的数最多只有 A 的前 k/2−1 个数和 B 的前 k/2−1 个数，
    // 即比 A[k/2−1] 小的数最多只有 k-2 个，因此 A[k/2−1] 不可能是第 k 个数，
    // A[0] 到 A[k/2−1] 也都不可能是第 k 个数，可以全部排除。
    // 如果 A[k/2−1]>B[k/2−1]，则可以排除 B[0] 到 B[k/2−1]。
    // 如果 A[k/2−1]=B[k/2−1]，则可以归入第一种情况处理。
    // 可以看到，比较 A[k/2−1] 和 B[k/2−1] 之后，可以排除 k/2 个不可能是第 k 小的数，查找范围缩小了一半。
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int length1 = nums1.length, length2 = nums2.length;
        int totalLength = length1 + length2;
        if (totalLength % 2 == 1) {// 总长度为奇数，中位数索引为midIndex
            int midIndex = totalLength / 2;
            double median = getKthElement(nums1, nums2, midIndex + 1);
            return median;
        } else {// 总长度为偶数，中位数为索引midIndex1 + midIndex2的平均值
            int midIndex1 = totalLength / 2 - 1, midIndex2 = totalLength / 2;
            double median = (getKthElement(nums1, nums2, midIndex1 + 1) +
                    getKthElement(nums1, nums2, midIndex2 + 1)) / 2.0;
            return median;
        }
    }

    public int getKthElement(int[] nums1, int[] nums2, int k) {
        // 主要思路：要找到第 k (k>1) 小的元素，
        // 那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 进行比较
        // 这里的 "/" 表示整除
        // nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共计 k/2-1 个
        // nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共计 k/2-1 个
        // 取 pivot = min(pivot1, pivot2)，
        // 两个数组中小于等于 pivot 的元素共计不会超过 (k/2-1) + (k/2-1) <= k-2 个
        // 这样 pivot 本身最大也只能是第 k-1 小的元素
        // 如果 pivot = pivot1，那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。
        // 把这些元素全部 "删除"，剩下的作为新的 nums1 数组
        // 如果 pivot = pivot2，那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。
        // 把这些元素全部 "删除"，剩下的作为新的 nums2 数组
        // 由于我们 "删除" 了一些元素（这些元素都比第 k 小的元素要小），因此需要修改 k 的值，减去删除的数的个数
        int length1 = nums1.length, length2 = nums2.length;
        int index1 = 0, index2 = 0;

        while (true) {
            // 边界情况
            if (index1 == length1)
                return nums2[index2 + k - 1];
            if (index2 == length2)
                return nums1[index1 + k - 1];
            if (k == 1)
                return Math.min(nums1[index1], nums2[index2]);

            // 正常情况
            int half = k / 2;
            int newIndex1 = Math.min(index1 + half, length1) - 1;
            int newIndex2 = Math.min(index2 + half, length2) - 1;
            int pivot1 = nums1[newIndex1], pivot2 = nums2[newIndex2];
            if (pivot1 <= pivot2) {// 排除 A[index1] 到 A[k/2−1]
                k -= (newIndex1 - index1 + 1);
                index1 = newIndex1 + 1;// A数组下标移动
            } else {// 排除 B[index2] 到 B[k/2−1]
                k -= (newIndex2 - index2 + 1);
                index2 = newIndex2 + 1;// B数组下标移动
            }
        }
    }

    // 方法一：（自己写的）二分查找-时间复杂度：O(log(m+n))，空间复杂度：O(1)
    public double findMedianSortedArrays11(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int nums1Left = 0, nums2Left = 0;
        int needRemoved = (m + n - 1) / 2;
        while (needRemoved > 0) {
            int removed = Math.max(needRemoved / 2, 1);
            int nums1Mid = nums1Left + removed - 1;
            int nums2Mid = nums2Left + removed - 1;
            int num1 = nums1Mid < m ? nums1[nums1Mid] : Integer.MAX_VALUE;
            int num2 = nums2Mid < n ? nums2[nums2Mid] : Integer.MAX_VALUE;
            if (num1 <= num2)
                nums1Left = nums1Mid + 1;
            else
                nums2Left = nums2Mid + 1;
            needRemoved -= removed;
        }

        PriorityQueue<Integer> pq = new PriorityQueue<>();
        if (nums1Left < m)
            pq.offer(nums1[nums1Left]);
        if (nums1Left + 1 < m)
            pq.offer(nums1[nums1Left + 1]);
        if (nums2Left < n)
            pq.offer(nums2[nums2Left]);
        if (nums2Left + 1 < n)
            pq.offer(nums2[nums2Left + 1]);

        if (((m + n) & 1) == 1)
            return pq.poll();
        else
            return (pq.poll() + pq.poll()) / 2.0;
    }

    // 方法二：划分数组（其实也是二分）-时间复杂度：O(logmin(m,n))，空间复杂度：O(1)
    // 划分思想：中位数，即是将一个集合划分为两个长度相等的子集，其中一个子集中的元素总是大于另一个子集中的元素。
    // nums1 num2分别拆为左右两部分，左右两部分分别合并，得到A, B
    // 当 A 和 B 的总长度是偶数时：
    // 保证A B长度相等，median = (A最大 + B最小) / 2
    // 当 A 和 B 的总长度是奇数时：
    // 保证 len(A) = len(B) + 1，median = A最大
    // i, j 是nums1 num2的拆分点
    // 则：
    // i+j=m−i+n−j（当 m+n 为偶数）或 i+j+1=m−i+n−j（当 m+n 为奇数）二分搜索i值
    // 还要保证：前一部分的最大值小于等于后一部分的最小值
    public double findMedianSortedArrays2(int[] nums1, int[] nums2) {
        // 保证第一个数组长度比第二个数组短(或者相等)，因为二分查找是以nums1的边界作为参考，nums2根据恒等式得到j的值
        // 如果nums1长度大于nums2，那么j可能会计算出为负
        if (nums1.length > nums2.length)
            return findMedianSortedArrays2(nums2, nums1);

        int m = nums1.length;
        int n = nums2.length;
        int left = 0, right = m;
        // median1：前一部分的最大值
        // median2：后一部分的最小值
        int firstHalfMax = 0, secondHalfMin = 0;

        while (left <= right) {
            // 前一部分包含 nums1[0 .. i-1] 和 nums2[0 .. j-1]
            // 后一部分包含 nums1[i .. m-1] 和 nums2[j .. n-1]
            int i = (left + right) / 2;// 二分搜索i值
            int j = (m + n) / 2 - i;

            // nums_im1, nums_i, nums_jm1, nums_j
            // 分别表示 nums1[i-1], nums1[i], nums2[j-1], nums2[j]
            // 用最小最大值充当边界nums[-1] num[m or n]
            int nums_im1 = (i == 0 ? Integer.MIN_VALUE : nums1[i - 1]);
            int nums_i = (i == m ? Integer.MAX_VALUE : nums1[i]);
            int nums_jm1 = (j == 0 ? Integer.MIN_VALUE : nums2[j - 1]);
            int nums_j = (j == n ? Integer.MAX_VALUE : nums2[j]);

            if (nums_im1 <= nums_j) {// nums1[i-1]<= nums2[j] 这是满足数组划分的一种情况，记录此时的中位数
                firstHalfMax = Math.max(nums_im1, nums_jm1);
                secondHalfMin = Math.min(nums_i, nums_j);
                left = i + 1;
            } else
                right = i - 1;
        }

        return (m + n) % 2 == 0 ? (firstHalfMax + secondHalfMin) / 2.0 : secondHalfMin;
    }

    // 5. 最长回文子串
    // 给你一个字符串 s，找到 s 中最长的回文子串。
    // 如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
    // 提示：
    // 1 <= s.length <= 1000
    // s 仅由数字和英文字母组成

    // 方法一：动态规划（有点强行了）-时间复杂度：O(n^2)，空间复杂度：O(n^2)

    // 方法二：（自己写的）中心拓展-时间复杂度：O(n^2)，空间复杂度：O(1)
    public String longestPalindrome(String s) {
        if (s.length() == 1)
            return s;
        String res = "";
        for (int i = 0; i < s.length() - 1; i++) {
            String ans1 = getPalindrome(i, i, s);
            String ans2 = getPalindrome(i, i + 1, s);
            if (ans1.length() > res.length())
                res = ans1;
            if (ans2.length() > res.length())
                res = ans2;
        }
        return res;
    }

    private String getPalindrome(int left, int right, String s) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return s.substring(left + 1, right);
    }

    // 方法三：Manacher 算法-时间复杂度：O(n)，空间复杂度：O(n)
    // 定义一个新概念臂长，表示中心扩展算法向外扩展的长度。如果一个位置的最大回文字符串长度为 2 * length + 1 ，其臂长为 length。
    // 在中心扩展法的过程中记录右臂在最右边的回文字符串，将其中心作为 j，在计算过程中就能最大限度地避免重复计算。
    public String longestPalindrome3(String s) {
        int n = s.length();
        StringBuffer t = new StringBuffer("$#");
        // 解决回文串奇数长度和偶数长度的问题，处理方式是在所有的相邻字符中间插入 # ，这样可以保证所有找到的回文串都是奇数长度的
        for (int i = 0; i < n; ++i)
            t.append(s.charAt(i)).append('#');

        t.append('!');// 字符串边界外，再随便放两个不一样的字符，防越界。e.g. aba → $#a#b#a#!
        n = t.length();

        int[] armLen = new int[n];
        int j = 0, right = 0;// 维护「当前最大的回文的右端点right」以及这个回文右端点对应的回文中心
        int iMax = 0, maxArmLen = 0;// 最长回文串的回文中心和臂长

        for (int i = 2; i < n - 2; ++i) {
            // i 被包含在当前最大回文子串内(right与当前点的距离, i关于j对称的点的armLen值)，不被包含(0)
            // 这里将 right−i 和 armLen[对称点] 取小，是先要保证这个回文串在当前最大回文串内。
            armLen[i] = i <= right ? Math.min(right - i, armLen[j * 2 - i]) : 0;// 初始化（马拉车算法的精华所在）
            while (t.charAt(i + armLen[i] + 1) == t.charAt(i - armLen[i] - 1))// 中心拓展
                ++armLen[i];
            if (i + armLen[i] > right) {// 动态维护 iMax 和 rMax
                j = i;
                right = i + armLen[i];
            }
            if (armLen[i] > maxArmLen) {// 记录当前最长回文串
                iMax = i;
                maxArmLen = armLen[i];
            }
        }

        // 去掉# 返回答案
        StringBuffer ans = new StringBuffer();
        for (int i = iMax - maxArmLen; i < iMax + maxArmLen; ++i)
            if (t.charAt(i) != '#')
                ans.append(t.charAt(i));

        return ans.toString();
    }

    // 7. 整数反转
    // 给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
    // 如果反转后整数超过 32 位的有符号整数的范围 [−231,  231 − 1] ，就返回 0。
    // 假设环境不允许存储 64 位整数（有符号或无符号）。
    // 提示：
    // -231 <= x <= 231 - 1

    // 方法一：数学-时间复杂度：O(1)，空间复杂度：O(1)
    public int reverse(int x) {
        int rev = 0;
        while (x != 0) {
            // 不用判断 rev == Integer.MIN_VALUE / 10 || rev == Integer.MIN_VALUE / 10 的情况
            // Integer.MAX_VALUE 2^31-1 2147483647
            // Integer.MIN_VALUE -2^31 -2147483648
            if (rev < Integer.MIN_VALUE / 10 || rev > Integer.MAX_VALUE / 10)
                return 0;
            int digit = x % 10;
            x /= 10;
            rev = rev * 10 + digit;
        }
        return rev;
    }

    // 方法一：（自己写的）数学-时间复杂度：O(1)，空间复杂度：O(1)
    public int reverse11(int x) {
        int MAX_VALUE = Integer.MAX_VALUE;

        boolean isNegtive = x < 0 ? true : false;
        String str = String.valueOf(x);
        int res = 0;
        int end = isNegtive ? 1 : 0;
        for (int i = str.length() - 1; i >= end; i--) {
            int curr = str.charAt(i) - '0';
            if (res > MAX_VALUE / 10)
                return 0;

            // 其实是多余判断
            if (res == MAX_VALUE / 10) {
                if (isNegtive && curr > MAX_VALUE % 10 + 1)
                    return 0;
                if (!isNegtive && curr > MAX_VALUE % 10)
                    return 0;
            }
            res = res * 10 + curr;
        }
        if (isNegtive)
            res = -res;
        return res;
    }

    // 8. 字符串转换整数(atoi)
    // 请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。
    // 函数 myAtoi(string s) 的算法如下：
    // 读入字符串并丢弃无用的前导空格
    // 检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。
    // 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
    // 读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
    // 将前面步骤读入的这些数字转换为整数（即，"123" -> 123， "0032" -> 32）。如果没有读入数字，则整数为 0 。
    // 必要时更改符号（从步骤 2 开始）。
    // 如果整数数超过 32 位有符号整数范围 [−231,  231 − 1] ，需要截断这个整数，使其保持在这个范围内。
    // 具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。
    // 返回整数作为最终结果。
    // 注意：
    // 本题中的空白字符只包括空格字符 ' ' 。
    // 除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。
    // 提示：
    // 0 <= s.length <= 200
    // s 由英文字母（大写和小写）、数字（0-9）、' '、'+'、'-' 和 '.' 组成

    // 方法一：（自己写的）模拟 if else-时间复杂度：O(n)，空间复杂度：O(1)
    public int myAtoi(String s) {
        s = s.trim();
        int n = s.length();
        boolean hasSign = false, isNegtive = false;
        int res = 0;
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (c == '-') {
                if (hasSign)
                    break;
                hasSign = true;
                isNegtive = true;
            } else if (c == '+') {
                if (hasSign)
                    break;
                hasSign = true;
            } else if (Character.isDigit(c)) {
                hasSign = true;
                int cur = c - '0';
                if (res > Integer.MAX_VALUE / 10)
                    return isNegtive ? Integer.MIN_VALUE : Integer.MAX_VALUE;
                else if (res == Integer.MAX_VALUE / 10) {
                    if (isNegtive && cur >= -(Integer.MIN_VALUE % 10))
                        return Integer.MIN_VALUE;
                    if (!isNegtive && cur >= Integer.MAX_VALUE % 10)
                        return Integer.MAX_VALUE;
                }
                res = res * 10 + cur;
            } else
                break;
        }
        if (isNegtive)
            res = -res;
        return res;
    }

    // 方法二：有限状态机-时间复杂度：O(n)，空间复杂度：O(1)
    public int strToInt2(String str) {
        Automaton automaton = new Automaton();
        int length = str.length();
        for (int i = 0; i < length; ++i)
            automaton.get(str.charAt(i));

        return (int) (automaton.sign * automaton.ans);
    }

    class Automaton {
        public int sign = 1;// 符号标记
        public long ans = 0;
        private String state = "start";// 起始状态
        private Map<String, String[]> table = new HashMap<String, String[]>() {
            {
                // 状态转移方式 ' ' +/- number other
                // 起始状态
                put("start", new String[] { "start", "signed", "in_number", "end" });
                // 符号
                put("signed", new String[] { "end", "end", "in_number", "end" });
                // 数字
                put("in_number", new String[] { "end", "end", "in_number", "end" });
                // 终止状态
                put("end", new String[] { "end", "end", "end", "end" });
            }
        };

        // 状态转移
        public void get(char c) {
            state = table.get(state)[get_col(c)];
            if ("in_number".equals(state)) {// 数字状态，计算答案
                ans = ans * 10 + c - '0';
                ans = sign == 1 ? Math.min(ans, (long) Integer.MAX_VALUE) : Math.min(ans, -(long) Integer.MIN_VALUE);
            } else if ("signed".equals(state))// 符号状态，记录正负
                sign = c == '+' ? 1 : -1;

        }

        // 状态转移方式 ' ' +/- number other
        private int get_col(char c) {
            if (c == ' ')
                return 0;
            if (c == '+' || c == '-')
                return 1;
            if (Character.isDigit(c))
                return 2;
            return 3;
        }
    }

    // 9. 回文数
    // 给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
    // 回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
    // 例如，121 是回文，而 123 不是。
    // 提示：
    // -231 <= x <= 231 - 1
    // 进阶：你能不将整数转为字符串来解决这个问题吗？

    // 方法一：反转一半数字-时间复杂度：O(1)，空间复杂度：O(1)
    public boolean isPalindrome(int x) {
        // 特殊情况：
        // 如上所述，当 x < 0 时，x 不是回文数。
        // 同样地，如果数字的最后一位是 0，为了使该数字为回文，
        // 则其第一位数字也应该是 0
        // 只有 0 满足这一属性
        if (x < 0 || (x % 10 == 0 && x != 0))
            return false;

        int revertedNumber = 0;
        while (x > revertedNumber) {
            revertedNumber = revertedNumber * 10 + x % 10;
            x /= 10;
        }

        // 当数字长度为奇数时，我们可以通过 revertedNumber/10 去除处于中位的数字。
        // 例如，当输入为 12321 时，在 while 循环的末尾我们可以得到 x = 12，revertedNumber = 123，
        // 由于处于中位的数字不影响回文（它总是与自己相等），所以我们可以简单地将其去除。
        return x == revertedNumber || x == revertedNumber / 10;
    }

    // 方法一：（自己写的）整数反转 + 比较-时间复杂度：O(1)，空间复杂度：O(1)
    // 理论上不如官方题解，但实际耗时差不多...
    public boolean isPalindrome11(int x) {
        if (x < 0)
            return false;
        int originalNum = x;
        long newNum = 0;
        while (x != 0) {
            newNum = newNum * 10 + x % 10;
            x = x / 10;
        }
        return originalNum == newNum;
    }

    // 11. 盛最多水的容器
    // 给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
    // 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
    // 返回容器可以储存的最大水量。
    // 说明：你不能倾斜容器。
    // 提示：
    // n == height.length
    // 2 <= n <= 105
    // 0 <= height[i] <= 104

    // 方法一：（自己写的）双指针-时间复杂度：O(n)，空间复杂度：O(1)
    public int maxArea(int[] height) {
        int left = 0, right = height.length - 1;
        int res = 0;
        while (left < right) {
            int leftHeight = height[left], rightHeight = height[right];
            int currHeight = Math.min(leftHeight, rightHeight);
            res = Math.max(res, (right - left) * currHeight);
            if (leftHeight < rightHeight)
                left++;
            else
                right--;
        }
        return res;
    }

    // 14. 最长公共前缀
    // 编写一个函数来查找字符串数组中的最长公共前缀。
    // 如果不存在公共前缀，返回空字符串 ""。
    // 提示：
    // 1 <= strs.length <= 200
    // 0 <= strs[i].length <= 200
    // strs[i] 仅由小写英文字母组成

    // 方法一：（自己写的）横向扫描-时间复杂度：O(mn)，空间复杂度：O(1)，其中 m 是字符串数组中的字符串的平均长度，n 是字符串的数量。
    // 依次遍历字符串数组中的每个字符串，对于每个遍历到的字符串，更新最长公共前缀，
    // 当遍历完所有的字符串以后，即可得到字符串数组中的最长公共前缀。
    // 官方写的复杂了...
    public String longestCommonPrefix(String[] strs) {
        String ans = strs[0];
        int end = ans.length();
        for (int i = 1; i < strs.length; i++) {
            String str = strs[i];
            for (int j = 0; j < Math.min(end, str.length()); j++) {
                if (str.charAt(j) != ans.charAt(j)) {
                    end = j;
                    break;
                }
            }
            end = Math.min(end, str.length());
        }

        return ans.substring(0, end);
    }

    // 方法二：纵向扫描-时间复杂度：O(mn)，空间复杂度：O(1)，其中 m 是字符串数组中的字符串的平均长度，n 是字符串的数量。
    // 从前往后遍历所有字符串的每一列，比较相同列上的字符是否相同，
    // 如果相同则继续对下一列进行比较，如果不相同则当前列不再属于公共前缀，当前列之前的部分为最长公共前缀。
    public String longestCommonPrefix2(String[] strs) {
        if (strs == null || strs.length == 0)
            return "";

        int length = strs[0].length();
        int count = strs.length;
        for (int i = 0; i < length; i++) {
            char c = strs[0].charAt(i);
            for (int j = 1; j < count; j++)
                if (i == strs[j].length() || strs[j].charAt(i) != c)
                    return strs[0].substring(0, i);
        }
        return strs[0];
    }

    // 方法三：dfs 分治-时间复杂度：O(mn)，空间复杂度：O(mlogn)，其中 m 是字符串数组中的字符串的平均长度，n 是字符串的数量。
    public String longestCommonPrefix3(String[] strs) {
        if (strs == null || strs.length == 0)
            return "";
        else
            return longestCommonPrefix(strs, 0, strs.length - 1);

    }

    public String longestCommonPrefix(String[] strs, int start, int end) {
        if (start == end)
            return strs[start];
        else {
            int mid = (end - start) / 2 + start;
            String lcpLeft = longestCommonPrefix(strs, start, mid);
            String lcpRight = longestCommonPrefix(strs, mid + 1, end);
            return commonPrefix(lcpLeft, lcpRight);
        }
    }

    public String commonPrefix(String lcpLeft, String lcpRight) {
        int minLength = Math.min(lcpLeft.length(), lcpRight.length());
        for (int i = 0; i < minLength; i++)
            if (lcpLeft.charAt(i) != lcpRight.charAt(i))
                return lcpLeft.substring(0, i);

        return lcpLeft.substring(0, minLength);
    }

    // 方法四：二分查找-时间复杂度：O(mnlogm)，空间复杂度：O(mlogn)，其中 m 是字符串数组中的字符串的平均长度，n 是字符串的数量。
    // 最长公共前缀的长度不会超过字符串数组中的最短字符串的长度。
    // 用 minLength 表示字符串数组中的最短字符串的长度，则可以在 [0,minLength] 的范围内通过二分查找得到最长公共前缀的长度。
    public String longestCommonPrefix4(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        int minLength = Integer.MAX_VALUE;
        for (String str : strs) {
            minLength = Math.min(minLength, str.length());
        }
        int low = 0, high = minLength;
        while (low < high) {
            int mid = (high - low + 1) / 2 + low;
            if (isCommonPrefix(strs, mid)) {
                low = mid;
            } else {
                high = mid - 1;
            }
        }
        return strs[0].substring(0, low);
    }

    public boolean isCommonPrefix(String[] strs, int length) {
        String str0 = strs[0].substring(0, length);
        int count = strs.length;
        for (int i = 1; i < count; i++) {
            String str = strs[i];
            for (int j = 0; j < length; j++) {
                if (str0.charAt(j) != str.charAt(j)) {
                    return false;
                }
            }
        }
        return true;
    }

    // 方法五：（自己写的）排序 + 比较最短最长-时间复杂度：O(mnlogn)，空间复杂度：O(logn)，其中 m 是字符串数组中的字符串的平均长度，n
    // 是字符串的数量。
    public String longestCommonPrefix5(String[] strs) {
        Arrays.sort(strs);
        String str1 = strs[0];
        String str2 = strs[strs.length - 1];
        for (int i = 0; i < str1.length(); i++)
            if (str1.charAt(i) != str2.charAt(i))
                return str1.substring(0, i);

        return str1;
    }

    // 15. 三数之和
    // 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]]
    // 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。
    // 请你返回所有和为 0 且不重复的三元组。
    // 注意：答案中不可以包含重复的三元组。
    // 提示：
    // 3 <= nums.length <= 3000
    // -105 <= nums[i] <= 105

    // 方法一：排序 + 双指针（有点牵强）-时间复杂度：O(n^2)，空间复杂度：O(logn)
    // 不包含重复的三元组的关键：需要和上一次枚举的数不相同
    public List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        // a + b + c = 0
        // 枚举 a
        for (int first = 0; first < n; ++first) {
            // 需要和上一次枚举的数不相同
            if (first > 0 && nums[first] == nums[first - 1])
                continue;

            // c 对应的指针初始指向数组的最右端
            int third = n - 1;
            int target = -nums[first]; // b + c = -a = target
            // 枚举 b
            for (int second = first + 1; second < n; ++second) {
                // 需要和上一次枚举的数不相同
                if (second > first + 1 && nums[second] == nums[second - 1])
                    continue;

                // 需要保证 b 的指针在 c 的指针的左侧
                while (second < third && nums[second] + nums[third] > target)
                    --third;

                // 如果指针重合，随着 b 后续的增加
                // 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
                if (second == third)
                    break;

                // 所得即答案
                if (nums[second] + nums[third] == target) {
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(nums[first]);
                    list.add(nums[second]);
                    list.add(nums[third]);
                    ans.add(list);
                }
            }
        }
        return ans;
    }

    // 方法一：自己写的（真正的双指针）-时间复杂度：O(n^2)，空间复杂度：O(logn)
    public List<List<Integer>> threeSum11(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (i > 0 && nums[i] == nums[i - 1])
                continue;
            int a = nums[i];
            int leftIndex = i + 1;
            int rightIndex = n - 1;
            while (leftIndex < rightIndex) {
                int left = nums[leftIndex];
                int right = nums[rightIndex];
                int sum = a + left + right;
                if (sum == 0) {
                    res.add(new ArrayList<>(Arrays.asList(a, left, right)));
                    // 避免出现重复答案
                    while (leftIndex < n && nums[leftIndex] == left)
                        leftIndex++;
                } else if (sum > 0)
                    rightIndex--;
                else
                    leftIndex++;
            }
        }
        return res;
    }

    // 方法二：排序 + 二分查找-时间复杂度：O(n^2logn)，空间复杂度：O(logn)
    public List<List<Integer>> threeSum2(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<List<Integer>>();

        // 枚举 a
        for (int first = 0; first < n; ++first) {
            // 需要和上一次枚举的数不相同
            if (first > 0 && nums[first] == nums[first - 1])
                continue;

            // a + b + c = 0, b + c = -a = target
            int target = -nums[first];
            // 枚举 b
            for (int second = first + 1; second < n; ++second) {
                // 需要和上一次枚举的数不相同
                if (second > first + 1 && nums[second] == nums[second - 1])
                    continue;

                // 随着 b 后续的增加，不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
                if (nums[second] > target / 2)
                    break;

                // 需要保证 b 的指针在 c 的指针的左侧
                int third = Arrays.binarySearch(nums, second + 1, n, target - nums[second]);

                // 没找到当前b对应的c，返回的是 -(应当插入的位置)-1
                if (third < 0)
                    continue;

                // third>=0，则找到了对应的c
                // 所得即答案
                List<Integer> list = Arrays.asList(nums[first], nums[second], nums[third]);// （一般还要放入实现类的构造器中，asList返回的是内部类）
                ans.add(list);
            }
        }
        return ans;
    }

    // 16. 最接近的三数之和
    // 给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
    // 返回这三个数的和。
    // 假定每组输入只存在恰好一个解。
    // 提示：
    // 3 <= nums.length <= 1000
    // -1000 <= nums[i] <= 1000
    // -104 <= target <= 104

    // 方法一：（自己写的）排序 + 双指针-时间复杂度：O(n^2)，空间复杂度：O(logn)
    // 官方优化了在双指针移动，会移动到不重复值上，但耗时并没有减少...
    public int threeSumClosest(int[] nums, int target) {
        int n = nums.length;
        int res = nums[0] + nums[1] + nums[2];
        Arrays.sort(nums);
        for (int i = 0; i < n; i++) {
            if (i > 0 && nums[i] == nums[i - 1])
                continue;
            int numi = nums[i];
            int left = i + 1, right = n - 1;
            while (left < right) {
                int curSum = numi + nums[left] + nums[right];
                if (Math.abs(curSum - target) < Math.abs(res - target))
                    res = curSum;
                if (curSum == target)
                    return res;
                else if (curSum > target)
                    right--;
                else
                    left++;
            }
        }
        return res;
    }

    // 20. 有效的括号
    // 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
    // 有效字符串需满足：
    // 左括号必须用相同类型的右括号闭合。
    // 左括号必须以正确的顺序闭合。
    // 每个右括号都有一个对应的相同类型的左括号。
    // 提示：
    // 1 <= s.length <= 104
    // s 仅由括号 '()[]{}' 组成

    // 方法一：（自己写的）栈-时间复杂度：O(n)，空间复杂度：O(n)
    public boolean isValid(String s) {
        Deque<Character> stk = new ArrayDeque<>();
        Map<Character, Character> map = new HashMap<>() {
            {
                put(']', '[');
                put(')', '(');
                put('}', '{');
            }
        };
        for (char c : s.toCharArray()) {
            if (map.containsKey(c)) {
                if (!map.isEmpty() && stk.peek() == map.get(c))
                    stk.poll();
                else
                    return false;
            } else
                stk.push(c);
        }
        return stk.isEmpty();
    }

    // 21. 合并两个有序链表
    // 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
    // 提示：
    // 两个链表的节点数目范围是 [0, 50]
    // -100 <= Node.val <= 100
    // l1 和 l2 均按 非递减顺序 排列

    // 方法一：（自己写的）迭代-时间复杂度：O(m+n)，空间复杂度：O(1)
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummyHead = new ListNode(-1);
        ListNode curr = dummyHead;
        while (list1 != null || list2 != null) {
            int list1Val = list1 == null ? Integer.MAX_VALUE : list1.val;
            int list2Val = list2 == null ? Integer.MAX_VALUE : list2.val;
            if (list1Val < list2Val) {
                curr.next = list1;
                list1 = list1.next;
            } else {
                curr.next = list2;
                list2 = list2.next;
            }
            curr = curr.next;
        }
        return dummyHead.next;
    }

    // 方法二：dfs 递归-时间复杂度：O(m+n)，空间复杂度：O(m+n)
    public ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
        if (l1 == null)
            return l2;
        else if (l2 == null)
            return l1;
        else if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }

    // 23. 合并K个升序链表
    // 给你一个链表数组，每个链表都已经按升序排列。
    // 请你将所有链表合并到一个升序链表中，返回合并后的链表。
    // 提示：
    // k == lists.length
    // 0 <= k <= 10^4
    // 0 <= lists[i].length <= 500
    // -10^4 <= lists[i][j] <= 10^4
    // lists[i] 按 升序 排列
    // lists[i].length 的总和不超过 10^4

    // 方法一：（自己写的）优先队列-时间复杂度：O(kn×logk)，空间复杂度：O(k)
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> pq = new PriorityQueue<>((l1, l2) -> l1.val - l2.val);
        ListNode dummyHead = new ListNode(-1);
        ListNode curr = dummyHead;
        for (ListNode list : lists)
            if (list != null)
                pq.offer(list);

        while (!pq.isEmpty()) {
            ListNode min = pq.poll();
            curr.next = min;
            curr = curr.next;
            if (min.next != null)
                pq.offer(min.next);
        }
        return dummyHead.next;
    }

    // 方法二：分治合并-时间复杂度为 O(kn×logk)，空间复杂度：O(logk)
    // 优化方法一，用分治的方法进行合并。（思路：归并排序）
    public ListNode mergeKLists2(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }

    // l r为链表数组的索引
    public ListNode merge(ListNode[] lists, int l, int r) {
        if (l == r)
            return lists[l];

        if (l > r)
            return null;

        int mid = (l + r) >> 1;
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }

    // 方法三：顺序合并-时间复杂度为 O(k^2 n)，空间复杂度：O(1)
    // （合并k个升序链表分解为多次合并两个升序链表）
    // 用一个变量 ans 来维护以及合并的链表，第 i 次循环把第 i 个链表和 ans 合并，答案保存到 ans 中。

    // 26. 删除有序数组中的重复项
    // 给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持一致
    // 由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k
    // 个元素应该保存最终结果。
    // 将最终结果插入 nums 的前 k 个位置后返回 k 。
    // 不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

    // 方法一：双指针-时间复杂度：O(n)，空间复杂度：O(1)
    public int removeDuplicates(int[] nums) {
        int n = nums.length;
        if (n == 0)
            return 0;

        int fast = 1, slow = 1;
        while (fast < n) {
            if (nums[fast] != nums[fast - 1])
                nums[slow++] = nums[fast];
            fast++;
        }
        return slow;
    }

    // 33. 搜索旋转排序数组（无重复）
    // 整数数组 nums 按升序排列，数组中的值 互不相同 。
    // 在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，
    // 使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ...,
    // nums[k-1]]（下标 从 0 开始 计数）。
    // 例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
    // 给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
    // 提示：
    // 1 <= nums.length <= 5000
    // -10^4 <= nums[i] <= 10^4
    // nums 中的每个值都 独一无二
    // 题目数据保证 nums 在预先未知的某个下标上进行了旋转
    // -10^4 <= target <= 10^4
    // 进阶：你可以设计一个时间复杂度为 O(log n) 的解决方案吗？

    // 方法一：（自己写的，完整情况讨论，冗余但易读）二分查找-时间复杂度：O(logn)，空间复杂度： O(1)
    public int search11(int[] nums, int target) {
        int n = nums.length;
        int left = 0;
        int right = n - 1;
        int firstVal = nums[0];
        // e.g. 4 5 6(t) 7 1 2(t) 3
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target)
                return mid;
            else if (nums[mid] > target) {// 当前值大于target
                if (target >= firstVal) // target在左（当前值大于target），此时情况唯一
                    right = mid - 1;
                else {// target在右边（当前值大于target）
                    if (nums[mid] < firstVal)// 当前值在左边（target在右边，当前值大于target）
                        right = mid - 1;
                    else // 当前值在右边（target在右边，当前值大于target）
                        left = mid + 1;
                }
            } else {// 当前值小于target
                if (target >= firstVal) {// target在左边（当前值小于target）
                    if (nums[mid] < firstVal)// 当前值在左边（target在左边，当前值小于target）
                        right = mid - 1;
                    else // 当前值在左边（target在左边，当前值小于target）
                        left = mid + 1;
                } else // target在右边（当前值小于target），此时情况唯一
                    left = mid + 1;
            }
        }
        return -1;
    }

    // 43. 字符串相乘
    // 给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
    // 注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
    // 提示：
    // 1 <= num1.length, num2.length <= 200
    // num1 和 num2 只能由数字组成。
    // num1 和 num2 都不包含任何前导零，除了数字0本身。

    // 方法一：模拟「竖式乘法」-时间复杂度：O(n1n2+n2^2)，空间复杂度：O(n1n2)
    // 从右往左遍历乘数，将乘数的每一位与被乘数相乘得到对应的结果，再将每次得到的结果累加。
    public String multiply(String num1, String num2) {
        // 如果 num1 或 num2 为0，则直接将 0 作为结果返回即可
        if (num1.equals("0") || num2.equals("0"))
            return "0";
        String ans = "0";
        int m = num1.length(), n = num2.length();
        for (int i = n - 1; i >= 0; i--) {
            StringBuffer curr = new StringBuffer();
            int add = 0;
            for (int j = n - 1; j > i; j--)
                curr.append(0);
            int y = num2.charAt(i) - '0';
            for (int j = m - 1; j >= 0; j--) {
                int x = num1.charAt(j) - '0';
                int product = x * y + add;
                curr.append(product % 10);
                add = product / 10;
            }
            if (add != 0)
                curr.append(add % 10);
            ans = addStrings(ans, curr.reverse().toString());
        }
        return ans;
    }

    public String addStrings(String num1, String num2) {
        int i = num1.length() - 1, j = num2.length() - 1, add = 0;
        StringBuffer ans = new StringBuffer();
        while (i >= 0 || j >= 0 || add != 0) {
            int x = i >= 0 ? num1.charAt(i) - '0' : 0;
            int y = j >= 0 ? num2.charAt(j) - '0' : 0;
            int result = x + y + add;
            ans.append(result % 10);
            add = result / 10;
            i--;
            j--;
        }
        ans.reverse();
        return ans.toString();
    }

    // 方法一：（自己写的）模拟「竖式乘法」（接近官方题解方法一）-时间复杂度：O(n1n2+n2^2)，空间复杂度：O(n1n2)
    public String multiply11(String num1, String num2) {
        int n1 = num1.length(), n2 = num2.length();
        if (n1 < n2)// 较短数做乘数
            return multiply11(num2, num1);

        ListNode[] nums = new ListNode[n2];
        int index = 0;
        for (int i = n2 - 1; i >= 0; i--) {
            int currNodeNum2 = num2.charAt(i) - '0';
            if (currNodeNum2 == 0) {
                nums[index++] = new ListNode(0);
                continue;
            }
            int carry = 0;
            ListNode dummyHead = new ListNode(-1);
            ListNode currNode = dummyHead;
            for (int j = n1 - 1; j >= 0; j--) {
                int currNodeNum1 = num1.charAt(j) - '0';
                int multiply = currNodeNum2 * currNodeNum1 + carry;
                carry = multiply / 10;
                currNode.next = new ListNode(multiply % 10);
                currNode = currNode.next;
            }
            if (carry != 0)
                currNode.next = new ListNode(carry);
            nums[index++] = dummyHead.next;
        }

        StringBuilder res = new StringBuilder();
        boolean flag = true;
        int carry = 0;
        while (flag) {
            int sum = carry;
            flag = false;
            for (int i = 0; i < Math.min(nums.length, res.length() + 1); i++) {
                ListNode currNode = nums[i];
                if (currNode == null)
                    continue;
                flag = true;
                sum += currNode.val;
                nums[i] = currNode.next;
            }
            if (!flag)
                break;
            res.append(sum % 10);
            carry = sum / 10;
        }
        if (carry != 0)
            res.append(carry);
        return res.reverse().toString();
    }

    // 方法二：优化方法一-时间复杂度：O(n1n2)，空间复杂度：O(n1n2)
    // 方法一的做法是从右往左遍历乘数，将乘数的每一位与被乘数相乘得到对应的结果，再将每次得到的结果累加，整个过程中涉及到较多字符串相加的操作。
    // 如果使用数组代替字符串存储结果，则可以减少对字符串的操作。
    public String multiply2(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0"))
            return "0";

        int m = num1.length(), n = num2.length();
        int[] ansArr = new int[m + n];
        for (int i = m - 1; i >= 0; i--) {
            int x = num1.charAt(i) - '0';
            for (int j = n - 1; j >= 0; j--) {
                int y = num2.charAt(j) - '0';
                ansArr[i + j + 1] += x * y;
            }
        }
        for (int i = m + n - 1; i > 0; i--) {
            ansArr[i - 1] += ansArr[i] / 10;
            ansArr[i] %= 10;
        }
        int index = ansArr[0] == 0 ? 1 : 0;// 如果最高位是 0 则舍弃最高位。
        StringBuffer ans = new StringBuffer();
        while (index < m + n) {
            ans.append(ansArr[index]);
            index++;
        }
        return ans.toString();
    }

    // 46. 全排列
    // 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
    // 提示：
    // 1 <= nums.length <= 6
    // -10 <= nums[i] <= 10
    // nums 中的所有整数 互不相同

    // 方法一：回溯 + 交换-时间复杂度：O(n×n!)，空间复杂度：O(n)
    // 核心思想：依次交换位置
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    List<Integer> output = new ArrayList<Integer>();
    int n;

    public List<List<Integer>> permute(int[] nums) {
        for (int num : nums)
            output.add(num);

        n = nums.length;
        backtrack(0);
        return res;
    }

    // 从左往右填到第 first 个位置
    public void backtrack(int first) {
        // 所有数都填完了
        if (first == n)
            res.add(new ArrayList<Integer>(output));

        for (int i = first; i < n; i++) {
            // 动态维护数组
            Collections.swap(output, first, i);// 第一次循环first = i，不交换
            // 继续递归填下一个数
            backtrack(first + 1);
            // 撤销操作
            Collections.swap(output, first, i);
        }
    }

    // 方法二：（自己写的）dfs 回溯-时间复杂度：O(n×n!)，空间复杂度：O(n)
    class tsolution46 {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> ans = new ArrayList<>();
        int n;
        int[] nums;
        boolean[] hasVisited;

        public List<List<Integer>> permute(int[] nums) {
            this.n = nums.length;
            this.nums = nums;
            this.hasVisited = new boolean[n];
            dfs(0);
            return res;
        }

        private void dfs(int index) {
            if (index == n) {
                res.add(new ArrayList<>(ans));
                return;
            }
            for (int i = 0; i < n; i++) {
                if (hasVisited[i])
                    continue;

                hasVisited[i] = true;
                ans.add(nums[i]);

                dfs(index + 1);

                hasVisited[i] = false;
                ans.remove(ans.size() - 1);
            }
        }
    }

    // 53. 最大子数组和
    // 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
    // 子数组 是数组中的一个连续部分。
    // 提示：
    // 1 <= nums.length <= 105
    // -104 <= nums[i] <= 104

    // 方法一：动态规划-时间复杂度：O(n)，空间复杂度：O(1)
    public int maxSubArray(int[] nums) {
        int pre = 0, maxAns = nums[0];
        for (int x : nums) {
            pre = Math.max(pre + x, x);
            maxAns = Math.max(maxAns, pre);
        }
        return maxAns;
    }

    // 方法二：（自己写的）分治（线段树）-时间复杂度：O(n)，空间复杂度：O(logn)
    public int maxSubArray2(int[] nums) {
        int[] res = dfs(0, nums.length - 1, nums);
        return Math.max(res[0], Math.max(res[1], res[2]));
    }

    // [leftMax, rightMax, innerMax, sum]
    private int[] dfs(int left, int right, int[] nums) {
        if (left == right)
            return new int[] { nums[left], nums[left], nums[left], nums[left] };

        int mid = (left + right) / 2;
        int[] leftRes = dfs(left, mid, nums);
        int[] rightRes = dfs(mid + 1, right, nums);

        int newLeftMax = Math.max(leftRes[0], Math.max(leftRes[3], leftRes[3] + rightRes[0]));
        int newRightMax = Math.max(rightRes[1], Math.max(rightRes[3], rightRes[3] + leftRes[1]));
        int newInnerMax = Math.max(leftRes[2], Math.max(rightRes[2], leftRes[1] + rightRes[0]));
        int newSum = leftRes[3] + rightRes[3];
        return new int[] { newLeftMax, newRightMax, newInnerMax, newSum };
    }

    // 54. 螺旋矩阵
    // 给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
    // 提示：
    // m == matrix.length
    // n == matrix[i].length
    // 1 <= m, n <= 10
    // -100 <= matrix[i][j] <= 100

    // 方法一：（设置移动方向）模拟-时间复杂度：O(mn)，空间复杂度：O(mn)
    // 可以模拟螺旋矩阵的路径。初始位置是矩阵的左上角，初始方向是向右，当路径超出界限或者进入之前访问过的位置时，顺时针旋转，进入下一个方向。
    // 判断路径是否进入之前访问过的位置需要使用一个与输入矩阵大小相同的辅助矩阵 visited，其中的每个元素表示该位置是否被访问过。
    // 当一个元素被访问时，将 visited 中的对应位置的元素设为已访问。
    // 如何判断路径是否结束？由于矩阵中的每个元素都被访问一次，因此路径的长度即为矩阵中的元素数量，当路径的长度达到矩阵中的元素数量时即为完整路径，将该路径返回。
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> order = new ArrayList<Integer>();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
            return order;

        int rows = matrix.length, columns = matrix[0].length;
        boolean[][] visited = new boolean[rows][columns];
        int total = rows * columns;
        int row = 0, column = 0;
        int[][] directions = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
        int directionIndex = 0;
        for (int i = 0; i < total; i++) {
            order.add(matrix[row][column]);
            visited[row][column] = true;
            int nextRow = row + directions[directionIndex][0], nextColumn = column + directions[directionIndex][1];
            if (nextRow < 0 || nextRow >= rows || nextColumn < 0 || nextColumn >= columns
                    || visited[nextRow][nextColumn])
                directionIndex = (directionIndex + 1) % 4;

            row += directions[directionIndex][0];
            column += directions[directionIndex][1];
        }
        return order;
    }

    // 方法二：按层模拟-时间复杂度：O(mn)，空间复杂度：O(1)
    public List<Integer> spiralOrder2(int[][] matrix) {
        List<Integer> order = new ArrayList<Integer>();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
            return order;

        int rows = matrix.length, columns = matrix[0].length;
        int left = 0, right = columns - 1, top = 0, bottom = rows - 1;
        while (left <= right && top <= bottom) {
            for (int column = left; column <= right; column++)
                order.add(matrix[top][column]);

            for (int row = top + 1; row <= bottom; row++)
                order.add(matrix[row][right]);

            if (left < right && top < bottom) {
                for (int column = right - 1; column > left; column--)
                    order.add(matrix[bottom][column]);
                for (int row = bottom; row > top; row--)
                    order.add(matrix[row][left]);
            }
            left++;
            right--;
            top++;
            bottom--;
        }
        return order;
    }

    // 方法二：（自己写的）按层模拟-时间复杂度：O(mn)，空间复杂度：O(1)
    public List<Integer> spiralOrder22(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int upRow = 0, downRow = m - 1;
        int leftColumn = 0, rightColumn = n - 1;
        List<Integer> res = new ArrayList<>();
        while (leftColumn <= rightColumn && upRow <= downRow) {
            for (int j = leftColumn; j <= rightColumn; j++)
                res.add(matrix[upRow][j]);

            for (int i = upRow + 1; i < downRow; i++)
                res.add(matrix[i][rightColumn]);

            if (upRow == downRow)
                break;
            for (int j = rightColumn; j >= leftColumn; j--)
                res.add(matrix[downRow][j]);

            if (leftColumn == rightColumn)
                break;
            for (int i = downRow - 1; i > upRow; i--)
                res.add(matrix[i][leftColumn]);

            upRow++;
            downRow--;
            leftColumn++;
            rightColumn--;
        }
        return res;
    }

    // 59. 螺旋矩阵II
    // 给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
    // 提示：
    // 1 <= n <= 20

    // 方法一：模拟-时间复杂度：O(n^2)，空间复杂度：O(1)
    public int[][] generateMatrix(int n) {
        int maxNum = n * n;
        int curNum = 1;
        int[][] matrix = new int[n][n];
        int row = 0, column = 0;
        int[][] directions = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } }; // 右下左上
        int directionIndex = 0;
        while (curNum <= maxNum) {
            matrix[row][column] = curNum;
            curNum++;
            int nextRow = row + directions[directionIndex][0], nextColumn = column + directions[directionIndex][1];
            if (nextRow < 0 || nextRow >= n || nextColumn < 0 || nextColumn >= n || matrix[nextRow][nextColumn] != 0) {
                directionIndex = (directionIndex + 1) % 4; // 顺时针旋转至下一个方向
            }
            row = row + directions[directionIndex][0];
            column = column + directions[directionIndex][1];
        }
        return matrix;
    }

    // 方法二：按层模拟-时间复杂度：O(n^2)，空间复杂度：O(1)
    public int[][] generateMatrix2(int n) {
        int num = 1;
        int[][] matrix = new int[n][n];
        int left = 0, right = n - 1, top = 0, bottom = n - 1;
        while (left <= right && top <= bottom) {
            for (int column = left; column <= right; column++)
                matrix[top][column] = num++;

            for (int row = top + 1; row <= bottom; row++)
                matrix[row][right] = num++;

            if (left < right && top < bottom) {
                for (int column = right - 1; column > left; column--)
                    matrix[bottom][column] = num++;
                for (int row = bottom; row > top; row--)
                    matrix[row][left] = num++;
            }
            left++;
            right--;
            top++;
            bottom--;
        }
        return matrix;
    }

    // 61. 旋转链表
    // 给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
    // 提示：
    // 链表中节点的数目在范围 [0, 500] 内
    // -100 <= Node.val <= 100
    // 0 <= k <= 2 * 109

    // 方法一：（自己写的）遍历链表-时间复杂度：O(n)，空间复杂度：O(1)
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k == 0)// 特殊情况没有旋转，直接返回
            return head;

        // 1. 先遍历一遍链表得到链表长度，提示k远大于链表长度，需要提前缩减k值
        int n = 0;
        ListNode fast = head;
        while (fast != null) {
            fast = fast.next;
            n++;
        }

        // 2. 找到新的头结点和尾结点
        fast = head;
        k = k % n;
        while (k != 0) {
            fast = fast.next;
            k--;
        }

        if (fast == head) // 此时链表没有旋转，直接返回
            return head;

        ListNode slow = head;
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }

        ListNode newHead = slow.next;
        fast.next = head;
        ListNode tail = slow;
        tail.next = null;
        return newHead;
    }

    // 62. 不同路径
    // 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
    // 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
    // 问总共有多少条不同的路径？
    // 提示：
    // 1 <= m, n <= 100
    // 题目数据保证答案小于等于 2 * 109

    // 方法一：（自己写的）动态规划-时间复杂度：O(mn)，空间复杂度：O(n)
    public int uniquePaths(int m, int n) {
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        for (int i = 1; i < m; i++)
            for (int j = 1; j < n; j++)
                dp[j] = dp[j - 1] + dp[j];

        return dp[n - 1];
    }

    // 方法二：组合数学-时间复杂度：O(m)，空间复杂度：O(1)
    // C(m-1, m-1+n-1)
    public int uniquePaths2(int m, int n) {
        long ans = 1;
        for (int x = n, y = 1; y < m; ++x, ++y)
            ans = ans * x / y;

        return (int) ans;
    }

    // 70. 爬楼梯
    // 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
    // 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
    // 提示：
    // 1 <= n <= 45

    // 方法一：动态规划-时间复杂度：O(n)，空间复杂度：O(1)
    // f(x) = f(x−1) + f(x−2)
    public int climbStairs(int n) {
        int p = 0, q = 0, r = 1;// 滚动数组，节省内存开销
        for (int i = 1; i <= n; ++i) {
            p = q;
            q = r;
            r = p + q;
        }
        return r;
    }

    // 方法二：矩阵快速幂-时间复杂度：同快速幂，O(logn)，空间复杂度：O(1)
    // f(n) = q^n * [f(1) f(0)]T
    // 快速计算矩阵 q 的 n 次幂，就可以得到 f(n) 的值。如果直接求取 q^n ，时间复杂度是 O(n) ，
    // 我们可以定义矩阵乘法，然后用快速幂算法来加速这里 q^n 的求取

    public int climbStairs2(int n) {
        int[][] q = { { 1, 1 }, { 1, 0 } };
        int[][] res = pow(q, n);
        return res[0][0];
    }

    // 快速幂
    public int[][] pow(int[][] a, int n) {
        int[][] ret = { { 1, 0 }, { 0, 1 } };
        while (n > 0) {
            if ((n & 1) == 1)
                ret = multiply(ret, a);

            n >>= 1;
            a = multiply(a, a);
        }
        return ret;
    }

    // 矩阵乘法
    public int[][] multiply(int[][] a, int[][] b) {
        int[][] c = new int[2][2];
        for (int i = 0; i < 2; i++)
            for (int j = 0; j < 2; j++)
                c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];

        return c;
    }

    // 方法三：通项公式-时空复杂度与pow函数和CPU 支持的指令集相关，这里不深入分析
    public int climbStairs3(int n) {
        double sqrt5 = Math.sqrt(5);
        double fibn = Math.pow((1 + sqrt5) / 2, n + 1) - Math.pow((1 - sqrt5) / 2, n + 1);
        return (int) Math.round(fibn / sqrt5);
    }

    // 78. 子集
    // 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
    // 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
    // 提示：
    // 1 <= nums.length <= 10
    // -10 <= nums[i] <= 10
    // nums 中的所有元素 互不相同
    // 方法一：迭代法实现子集枚举（位运算）-时间复杂度O(n×2^n)
    // 用 1 表示「在子集中」，0 表示「不在子集中」
    // 可以发现 0/10/1 序列对应的二进制数正好从 0 到 2^n - 1
    // 可以枚举mask∈[0,2^n−1]，mask 的二进制表示是一个 0/1 序列，可以按照这个 0/1 序列在原集合当中取数。
    // 当枚举完所有 2^n-1 个mask，也就能构造出所有的子集
    List<List<Integer>> subsets(int[] nums) {
        List<Integer> t = new ArrayList<Integer>();
        List<List<Integer>> ans = new ArrayList<List<Integer>>();

        int n = nums.length;
        for (int mask = 0; mask < (1 << n); ++mask) {
            t.clear();// 表t清空
            for (int i = 0; i < n; ++i)
                if ((mask & (1 << i)) != 0)
                    t.add(nums[i]);// 从末尾位开始，若为第i位为1则在t中加入对应元素（共n位）
            ans.add(new ArrayList<Integer>(t));
        }
        return ans;
    }

    // 方法二：递归法实现子集枚举（回溯、剪枝）-时间复杂度O(n×2^n)
    // 类似于树的深度优先遍历
    // 0左子树 1右子树
    class tsolution78 {
        List<Integer> t = new ArrayList<Integer>();
        List<List<Integer>> ans = new ArrayList<List<Integer>>();

        List<List<Integer>> subsets(int[] nums) {
            dfs(0, nums);
            return ans;
        }

        void dfs(int cur, int[] nums) {
            if (cur == nums.length) {// 此时所有位已枚举完成，（回溯、剪枝）
                ans.add(new ArrayList<Integer>(t));
                return;
            }
            // 选择加入当前位置cur的元素
            t.add(nums[cur]);// 置于末尾
            dfs(cur + 1, nums);

            // 选择不加入当前位置cur的元素
            t.remove(t.size() - 1);// 移除末尾元素
            dfs(cur + 1, nums);
        }
    }

    // 88. 合并两个有序数组
    // 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
    // 请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
    // 注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。
    // 为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
    // 提示：
    // nums1.length == m + n
    // nums2.length == n
    // 0 <= m, n <= 200
    // 1 <= m + n <= 200
    // -109 <= nums1[i], nums2[j] <= 109
    // 进阶：你可以设计实现一个时间复杂度为 O(m + n) 的算法解决此问题吗？

    // 方法一：逆向双指针-时间复杂度：O(m+n)，空间复杂度：O(1)
    // 指针设置为从后向前遍历，每次取两者之中的较大者放进 A 的最后面。
    public void merge(int[] A, int m, int[] B, int n) {
        int pa = m - 1, pb = n - 1;
        int tail = m + n - 1;
        int cur;
        while (pa >= 0 || pb >= 0) {
            if (pa == -1)
                cur = B[pb--];
            else if (pb == -1)
                cur = A[pa--];
            else if (A[pa] > B[pb])
                cur = A[pa--];
            else
                cur = B[pb--];
            A[tail--] = cur;
        }
    }

    // 方法二：双指针-时间复杂度：O(m+n)，空间复杂度：O(m+n)
    // 合并到新数组，再复制到A数组
    public void merge2(int[] A, int m, int[] B, int n) {
        int[] C = new int[n + m];
        int aindex = 0, bindex = 0, cindex = 0;
        while (aindex < m && bindex < n) {
            if (A[aindex] < B[bindex])
                C[cindex++] = A[aindex++];
            else
                C[cindex++] = B[bindex++];
        }
        while (aindex != m)
            C[cindex++] = A[aindex++];
        while (bindex != n)
            C[cindex++] = B[bindex++];

        for (int i = 0; i < m + n; i++)
            A[i] = C[i];
    }

    // 方法三：直接合并后排序-时间复杂度：O((m+n)log(m+n))，空间复杂度：O(log(m+n))

    // 89. 格雷编码
    // n 位格雷码序列 是一个由 2n 个整数组成的序列，其中：
    // 每个整数都在范围 [0, 2n - 1] 内（含 0 和 2n - 1）
    // 第一个整数是 0
    // 一个整数在序列中出现 不超过一次
    // 每对 相邻 整数的二进制表示 恰好一位不同 ，且
    // 第一个 和 最后一个 整数的二进制表示 恰好一位不同
    // 给你一个整数 n ，返回任一有效的 n 位格雷码序列 。
    // 提示：
    // 1 <= n <= 16

    // 方法一：对称生成-时间复杂度：O(2^n)，空间复杂度：O(1)
    // n = 1 [0, 1]
    // n = 2 [00，01，11，10]
    // n = 3 [000, 001, 011, 010, 110, 111, 101, 100]
    // ....
    // 一位格雷码只有两个元素，【1， 0】
    // 因为格雷码 n 每增加1，包含的数字会翻倍，这里我们设n位格雷码包含c个数，前一个n为n'，所以c = 2c'
    // 所以这时n中的前c'个数是n'中的所有数字前面补0，相当于全部都是n`中的数字
    // n = 2 [ 00, 01, 11, 10]
    // n = 3 [000, 001, 011, 010] (前四个数)
    // 这时n中的后c'个数是n'中的所有数字前面补1，然后变为逆序
    // n = 2 [ 00, 01, 11, 10]
    // 补 1 [100, 101, 111, 110]
    // 逆 序 [110, 111, 101, 100] （后四个数）
    // 结果拼接
    // n = 3 [000, 001, 011, 010, 110, 111, 101, 100]
    public List<Integer> grayCode(int n) {
        List<Integer> ret = new ArrayList<Integer>();
        ret.add(0);
        for (int i = 1; i <= n; i++) {
            int m = ret.size();
            for (int j = m - 1; j >= 0; j--)
                ret.add(ret.get(j) | (1 << (i - 1)));
        }
        return ret;
    }

    // 方法二：二进制数转格雷码-时间复杂度：O(2^n)，空间复杂度：O(1)
    // 从方法一我们可以知道，不管n为几，当前n的格雷码中的前一半始终为n - 1的全部，所以这时我们可以忽略n在格雷码中的影响
    // 这时我们将格雷码编号：
    // [000, 001, 011, 010, 110, 111, 101, 100 ...]
    // 0, 1, 2, 3 , 4, 5, 6, 7, ...
    // 这里的0 ~ 7... 转换为二进制后我们成为二进制码，比如我们要求解5对应的格雷码，这里5对应的二进制码就是0101（5的二进制）
    // 二进制码对应的每一位就是小b，，格雷码每一位是g，这里讲解过程中在前面补0方便理解，这里的\/就是异或的运算
    // 0 0 1 0 1
    // 0 b3 b2 b1 b0
    // \/ \/ \/ \/
    // g3 g2 g1 g0
    // 0 1 1 1
    // 所以我们由5（0101）推出对应的格雷码为0111
    // 这里解释一下(i >> 1) ^ i，i>>1其实将i每一位向后移动一位，这时和i取异或，相当于和自己的后一位取余
    // b3 b2 b1 b0 (i)
    // 0 b3 b2 b1 (i >> 1)
    // g3 g2 g1 g0 (结果)
    // 0 1 0 1 (5)
    // 0 0 1 0 (5>>1)
    // 0 1 1 1 ((5>>1)^5 = 7)
    public List<Integer> grayCode2(int n) {
        List<Integer> ret = new ArrayList<Integer>();
        for (int i = 0; i < 1 << n; i++)
            ret.add((i >> 1) ^ i);

        return ret;
    }

    // 方法三：（自己写的）逐位取反 + 打表-时间复杂度：O(2^n)，空间复杂度：O(1)
    public List<Integer> grayCode3(int n) {
        int totalCount = 1 << n;
        boolean[] visited = new boolean[totalCount];
        List<Integer> res = new ArrayList<>();
        int cur = 0;
        visited[cur] = true;
        res.add(cur);
        while (res.size() != totalCount) {
            for (int i = 0; i < n; i++) {
                int num = cur ^ (1 << i);
                if (!visited[num]) {
                    visited[num] = true;
                    cur = num;
                    res.add(cur);
                    break;
                }
            }
        }
        return res;
    }

    // 104. 二叉树的最大深度
    // 给定一个二叉树，找出其最大深度。
    // 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
    // 说明: 叶子节点是指没有子节点的节点。

    // 方法一：DFS（后序遍历）-空间复杂度-O(h)
    int maxDepth(TreeNode root) {// 三元运算符比if-else更快
        return root == null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;// 省去创建局部变量
    }

    // 方法一：（自己写的）dfs（先序遍历）-空间复杂度-O(h)
    class tsolution104 {
        int res = 0;

        public int maxDepth(TreeNode root) {
            dfs(root, 1);
            return res;
        }

        private void dfs(TreeNode root, int curDepth) {
            if (root == null)
                return;
            res = Math.max(res, curDepth);
            dfs(root.left, curDepth + 1);
            dfs(root.right, curDepth + 1);
        }
    }

    // 方法二：BFS-空间复杂度-O(n)
    int maxDepth2(TreeNode root) {
        if (root == null)
            return 0;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        int ans = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left != null)
                    queue.offer(node.left);
                if (node.right != null)
                    queue.offer(node.right);
            }
            ans++;
        }
        return ans;
    }

    // 121. 买卖股票的最佳时机
    // 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
    // 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
    // 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
    // 提示：
    // 1 <= prices.length <= 105
    // 0 <= prices[i] <= 104

    // 方法一：暴力法-时间复杂度：O(n^2)，空间复杂度：O(1)

    // 方法二：一次遍历（应该不算动规，算贪心吧）-时间复杂度：O(n)，空间复杂度：O(1)
    public int maxProfit(int prices[]) {
        int minprice = Integer.MAX_VALUE;
        int maxprofit = 0;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < minprice)// 更新最小价
                minprice = prices[i];
            else if (prices[i] - minprice > maxprofit)// 更新最大收益
                maxprofit = prices[i] - minprice;

        }
        return maxprofit;
    }

    // 122. 买卖股票的最佳时机II
    // 给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
    // 在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
    // 返回 你能获得的 最大 利润 。
    // 提示：
    // 1 <= prices.length <= 3 * 104
    // 0 <= prices[i] <= 104

    // 方法一：动态规划-时间复杂度：O(n)，空间复杂度：O(1)
    // 「不能同时参与多笔交易」，因此每天交易结束后只可能存在手里有一支股票或者没有股票的状态
    class tsolution122 {
        public int maxProfit(int[] prices) {
            int n = prices.length;
            int dp0 = 0, dp1 = -prices[0];
            for (int i = 1; i < n; ++i) {
                int newDp0 = Math.max(dp0, dp1 + prices[i]);
                int newDp1 = Math.max(dp1, dp0 - prices[i]);
                dp0 = newDp0;
                dp1 = newDp1;
            }
            return dp0;
        }
    }

    // 方法二：贪心-时间复杂度：O(n)，空间复杂度：O(1)
    // 贪心算法只能用于计算最大利润，计算的过程并不是实际的交易过程。
    class tsolution122_2 {
        public int maxProfit(int[] prices) {
            int ans = 0;
            int n = prices.length;
            for (int i = 1; i < n; ++i)
                ans += Math.max(0, prices[i] - prices[i - 1]);
            return ans;
        }
    }

    // 124. 二叉树中的最大路径和
    // 路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。
    // 同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
    // 路径和 是路径中各节点值的总和。
    // 给你一个二叉树的根节点 root ，返回其 最大路径和 。
    // 提示：
    // 树中节点数目范围是 [1, 3 * 104]
    // -1000 <= Node.val <= 1000

    // 方法一：（自己写的）dfs-时间复杂度：O(n)，空间复杂度：O(n)
    class tsolution124 {
        int res = Integer.MIN_VALUE;

        public int maxPathSum(TreeNode root) {
            dfs(root);
            return res;
        }

        private int dfs(TreeNode root) {
            if (root == null)
                return 0;

            int leftVal = dfs(root.left);
            int rightVal = dfs(root.right);
            int rootVal = root.val;

            int leftRootVal = leftVal + rootVal;
            int rightRootVal = rightVal + rootVal;
            int leftRightRootVal = leftVal + rightVal + rootVal;

            int ans = Math.max(rootVal, Math.max(leftRootVal, rightRootVal));
            res = Math.max(res, Math.max(ans, leftRightRootVal));

            return ans;
        }
    }

    // 136. 只出现一次的数字
    // 给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
    // 你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
    // 提示：
    // 1 <= nums.length <= 3 * 104
    // -3 * 104 <= nums[i] <= 3 * 104
    // 除了某个元素只出现一次以外，其余每个元素均出现两次。

    // 方法一：位运算-时间复杂度：O(n)，空间复杂度：O(1)
    public int singleNumber(int[] nums) {
        int single = 0;
        for (int num : nums)
            single ^= num;

        return single;
    }

    // 141. 环形链表
    // 给你一个链表的头节点 head ，判断链表中是否有环。
    // 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
    // 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
    // 注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
    // 如果链表中存在环 ，则返回 true 。 否则，返回 false 。
    // 提示：
    // 链表中节点的数目范围是 [0, 104]
    // -105 <= Node.val <= 105
    // pos 为 -1 或者链表中的一个 有效索引 。
    // 进阶：你能用 O(1)（即，常量）内存解决此问题吗？

    // 方法一：哈希表-时间复杂度：O(N)，空间复杂度：O(N)
    public boolean hasCycle(ListNode head) {
        Set<ListNode> seen = new HashSet<ListNode>();
        while (head != null) {
            if (!seen.add(head)) // 添加失败
                return true;

            head = head.next;
        }
        return false;
    }

    // 方法二：（自己写的）快慢指针-时间复杂度：O(N)，空间复杂度：O(1)
    // 「Floyd 判圈算法」（又称龟兔赛跑算法）
    // 我们定义两个指针，一快一满。慢指针每次只移动一步，而快指针每次移动两步。
    // 初始时，慢指针在位置 head，而快指针在位置 head.next。
    // 这样一来，如果在移动的过程中，快指针反过来追上慢指针，就说明该链表为环形链表。
    // 否则快指针将到达链表尾部，该链表不为环形链表。
    public boolean hasCycle2(ListNode head) {
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (slow == fast)
                return true;
        }

        return false;
    }

    // 142. 环形链表II
    // 给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
    // 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
    // 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
    // 如果 pos 是 -1，则在该链表中没有环。
    // 注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
    // 不允许修改 链表。
    // 提示：
    // 链表中节点的数目范围在范围 [0, 104] 内
    // -105 <= Node.val <= 105
    // pos 的值为 -1 或者链表中的一个有效索引
    // 进阶：你是否可以使用 O(1) 空间解决此题？

    // 方法一：哈希表-时间复杂度：O(N)，空间复杂度：O(N)
    public ListNode detectCycle(ListNode head) {
        Set<ListNode> seen = new HashSet<ListNode>();
        while (head != null) {
            if (!seen.add(head)) // 添加失败
                return head;

            head = head.next;
        }
        return null;
    }

    // 方法二：快慢指针-时间复杂度：O(N)，空间复杂度：O(1)
    // 如果链表中存在环，则 fast 指针最终将再次与 slow 指针在环中相遇。
    // 设链表中环外部分的长度为 a。slow 指针进入环后，又走了 b 的距离与fast 相遇。
    // 此时，fast 指针已经走完了环的 n 圈，因此它走过的总距离为 a+n(b+c)+b=a+(n+1)b+nc。
    // 根据题意，任意时刻，fast 指针走过的距离都为 slow 指针的 2 倍。
    // 因此，我们有
    // a+(n+1)b+nc=2(a+b)⟹a=c+(n−1)(b+c)
    // 有了 a=c+(n-1)(b+c)a=c+(n−1)(b+c) 的等量关系，我们会发现：
    // 从相遇点到入环点的距离加上 n-1 圈的环长，恰好等于从链表头部到入环点的距离。

    // 因此，当发现 slow 与 fast 相遇时，我们再额外使用一个指针 ptr。起始，它指向链表头部；
    // 随后，它和 slow 每次向后移动一个位置。最终，它们会在入环点相遇。

    public ListNode detectCycle2(ListNode head) {
        if (head == null)
            return null;

        ListNode slow = head, fast = head;
        while (fast != null) {
            if (fast.next == null)
                return null;
            slow = slow.next;
            fast = fast.next.next;
            if (fast == slow) {// 含环，此时开始寻找入环节点
                ListNode ptr = head;
                while (ptr != slow) {
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr;
            }
        }
        return null;
    }

    // 146. LRU缓存
    // 请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。
    // 实现 LRUCache 类：
    // LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
    // int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
    // void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；
    // 如果不存在，则向缓存中插入该组 key-value 。
    // 如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
    // 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
    // 提示：
    // 1 <= capacity <= 3000
    // 0 <= key <= 10000
    // 0 <= value <= 105
    // 最多调用 2 * 105 次 get 和 put

    // 方法一：（自己写的）哈希表 + 双向链表-时间复杂度：O(1)，空间复杂度：O(capacity)
    // 在面试中这种设计题，面试官一般会期望读者能够自己实现一个简单的双向链表，而不是使用语言自带的、封装好的数据结构。
    // 在双向链表的实现中，使用一个伪头部（dummy head）和伪尾部（dummy tail）标记界限，
    // 这样在添加节点和删除节点的时候就不需要检查相邻的节点是否存在。
    class LRUCache {
        class DLinkListNode {
            int key;
            int value;
            DLinkListNode prev;
            DLinkListNode next;

            DLinkListNode() {

            }

            DLinkListNode(int key, int value) {
                this.key = key;
                this.value = value;
            }
        }

        DLinkListNode dummyHead, dummyTail;
        Map<Integer, DLinkListNode> map;
        int capacity;

        public LRUCache(int capacity) {
            this.capacity = capacity;
            dummyHead = new DLinkListNode();
            dummyTail = new DLinkListNode();
            dummyHead.next = dummyTail;
            dummyTail.prev = dummyHead;
            map = new HashMap<>();
        }

        private void delete(DLinkListNode node) {
            DLinkListNode prev = node.prev;
            DLinkListNode next = node.next;
            prev.next = next;
            next.prev = prev;
        }

        private void push(DLinkListNode node) {
            DLinkListNode prev = dummyTail.prev;
            DLinkListNode next = dummyTail;
            node.prev = prev;
            node.next = next;
            prev.next = node;
            next.prev = node;
        }

        public int get(int key) {
            if (map.containsKey(key)) {
                DLinkListNode node = map.get(key);
                delete(node);
                push(node);
                return node.value;
            }
            return -1;
        }

        public void put(int key, int value) {
            if (map.containsKey(key)) {
                DLinkListNode node = map.get(key);
                node.value = value;
                delete(node);
                push(node);
                return;
            }

            DLinkListNode node = new DLinkListNode(key, value);
            if (capacity == map.size()) {
                DLinkListNode deleteNode = dummyHead.next;
                delete(deleteNode);
                map.remove(deleteNode.key);
            }
            push(node);
            map.put(key, node);
        }
    }

    // 方法二：自己写的lowb，用java自带的LinkedHashMap-时间复杂度：O(1)，空间复杂度：O(capacity)
    class LRUCache2 {
        Map<Integer, Integer> cache;
        int capacity;
        int size;

        public LRUCache2(int capacity) {
            this.capacity = capacity;
            cache = new LinkedHashMap<>(capacity);
        }

        public int get(int key) {
            if (cache.containsKey(key)) {
                Integer value = cache.get(key);
                cache.remove(key);
                cache.put(key, value);
                return value;
            } else
                return -1;
        }

        public void put(int key, int value) {
            if (cache.containsKey(key)) {
                cache.remove(key);
                cache.put(key, value);
            } else {
                ++size;
                if (size > capacity) {
                    Set<Integer> keySet = cache.keySet();
                    Iterator<Integer> keyIterator = keySet.iterator();
                    cache.remove(keyIterator.next()); // 一定不用判断hasNext()
                    --size;
                }
                cache.put(key, value);
            }
        }
    }

    // 148. 排序链表
    // 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
    // 进阶：
    // 你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
    // 提示：
    // 链表中节点的数目在范围 [0, 5 * 104] 内
    // -105 <= Node.val <= 105

    // 「147. 对链表进行插入排序」要求使用插入排序的方法对链表进行排序，插入排序的时间复杂度是 O(n^2)，其中 n 是链表的长度。
    // 这道题考虑时间复杂度更低的排序算法。题目的进阶问题要求达到 O(nlogn) 的时间复杂度和 O(1) 的空间复杂度，
    // 时间复杂度是 O(nlogn) 的排序算法包括归并排序、堆排序和快速排序（快速排序的最差时间复杂度是 O(n^2)，
    // 其中最适合链表的排序算法是归并排序。

    // 方法一：自顶向下归并排序-时间复杂度：O(nlogn)，其中 n 是链表的长度。空间复杂度：O(n)（拷贝数组，这里则是归并后的链表长度）
    // 对链表自顶向下归并排序的过程如下。（参考数组的归并排序）
    // 找到链表的中点，以中点为分界，将链表拆分成两个子链表。
    // 寻找链表的中点可以使用快慢指针的做法，快指针每次移动 2 步，慢指针每次移动 1 步，
    // 当快指针到达链表末尾时，慢指针指向的链表节点即为链表的中点。
    // 对两个子链表分别排序。
    // 将两个排序后的子链表合并，得到完整的排序后的链表。可以使用「21. 合并两个有序链表」的做法，将两个有序的子链表进行合并。
    // 上述过程可以通过递归实现。
    // 递归的终止条件是链表的节点个数小于或等于 1，即当链表为空或者链表只包含 1 个节点时，不需要对链表进行拆分和排序。
    public ListNode sortList(ListNode head) {
        return sortList(head, null);
    }

    public ListNode sortList(ListNode head, ListNode tail) {
        if (head == null)
            return head;

        // 由于特殊的拆分方式，拆分到仅剩两个元素时，直接去掉末尾元素
        // 不可能拆分成一个元素
        if (head.next == tail) {
            head.next = null;
            return head;
        }

        // 使用快慢指针找到中点进行拆分
        ListNode slow = head, fast = head;
        while (fast != tail) {
            slow = slow.next;
            fast = fast.next;
            if (fast != tail)
                fast = fast.next;
        }
        // 这里的mid可以理解成向上取整，而不是一般归并中的向下取整
        ListNode mid = slow;
        // 拆分（方式稍有变化，为了防止死循环）
        ListNode list1 = sortList(head, mid);
        ListNode list2 = sortList(mid, tail);
        // 合并
        ListNode sorted = merge(list1, list2);
        return sorted;
    }

    // 合并两个有序链表（迭代）
    public ListNode merge(ListNode head1, ListNode head2) {
        ListNode dummyHead = new ListNode(0);
        ListNode temp = dummyHead, temp1 = head1, temp2 = head2;
        while (temp1 != null && temp2 != null) {
            if (temp1.val <= temp2.val) {
                temp.next = temp1;
                temp1 = temp1.next;
            } else {
                temp.next = temp2;
                temp2 = temp2.next;
            }
            temp = temp.next;
        }

        // 处理末尾
        if (temp1 != null)
            temp.next = temp1;
        else if (temp2 != null)
            temp.next = temp2;

        return dummyHead.next;
    }

    // 方法一：（自己写的）自顶向下归并排序-时间复杂度：O(nlogn)，空间复杂度：O(n)
    // 拆分更方便理解（一切参考数组的归并排序，链表的末尾看做是null，null是一个独立的节点）
    public ListNode sortList11(ListNode head) {
        return divide(head, null);
    }

    private ListNode divide(ListNode head, ListNode tail) {
        if (head == tail) {
            if (head != null)
                head.next = null;// 划分为单个节点时，next置为null，方便后续合并
            return head;
        }

        ListNode fast = head;
        ListNode slow = head;
        while (fast != tail && fast.next != tail) {
            fast = fast.next.next;
            slow = slow.next;
        }

        ListNode secondHead = slow.next;// 精髓所在，slow的next可能会被置为null，则提前获取后半部分的起始节点
        ListNode l1 = divide(head, slow);
        ListNode l2 = divide(secondHead, tail);

        return mergeTwoList(l1, l2);
    }

    private ListNode mergeTwoList(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(-1);
        ListNode cur = dummyHead;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }

        if (l1 == null)
            cur.next = l2;
        if (l2 == null)
            cur.next = l1;

        return dummyHead.next;
    }

    // 方法一：（自己写的）自顶向下归并排序-时间复杂度：O(nlogn)，空间复杂度：O(n)
    // 区别在于舍弃使用tail，在自顶划分时就置尾结点为null，后续向下划分默认尾结点也为null
    class lt100Solition_148 {
        public ListNode sortList(ListNode head) {
            if (head == null)
                return head;
            return dfs(head);
        }

        private ListNode dfs(ListNode head) {
            if (head.next == null)
                return head;
            ListNode dummyHead = new ListNode(-1);
            dummyHead.next = head;
            ListNode fast = dummyHead, slow = dummyHead;
            while (fast != null && fast.next != null) {
                fast = fast.next.next;
                slow = slow.next;
            }
            ListNode secondListHead = slow.next;
            slow.next = null;

            ListNode list1 = dfs(head);
            ListNode list2 = dfs(secondListHead);
            return merge(list1, list2);
        }

        private ListNode merge(ListNode list1, ListNode list2) {
            ListNode dummyHead = new ListNode(-1);
            ListNode prev = dummyHead;
            while (list1 != null || list2 != null) {
                int list1Val = list1 == null ? Integer.MAX_VALUE : list1.val;
                int list2Val = list2 == null ? Integer.MAX_VALUE : list2.val;
                if (list1Val < list2Val) {
                    prev.next = list1;
                    list1 = list1.next;
                } else {
                    prev.next = list2;
                    list2 = list2.next;
                }
                prev = prev.next;
            }
            return dummyHead.next;
        }
    }

    // 方法二：自底向上归并排序-时间复杂度：O(nlogn)，空间复杂度：O(1)
    // 使用自底向上的方法实现归并排序，则可以达到 O(1) 的空间复杂度。
    // 首先求得链表的长度 length，然后将链表拆分成子链表进行合并。
    public ListNode sortList2(ListNode head) {
        if (head == null)
            return head;

        // 1. 首先从头向后遍历,统计链表长度
        int length = 0; // 用于统计链表长度
        ListNode node = head;
        while (node != null) {
            length++;
            node = node.next;
        }

        // 2. 初始化 引入dummynode
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;

        // 3. 每次将链表拆分成若干个长度为subLen的子链表 , 并按照每两个子链表一组进行合并
        // subLen每次左移一位（即sublen = sublen*2） PS:位运算对CPU来说效率更高
        for (int subLen = 1; subLen < length; subLen <<= 1) {
            ListNode prev = dummyHead;
            ListNode curr = dummyHead.next; // curr用于记录拆分链表的位置

            while (curr != null) { // 如果链表没有被拆完
                // 3.1 拆分subLen长度的链表1
                ListNode head_1 = curr; // 第一个链表的头 即 curr初始的位置
                for (int i = 1; i < subLen && curr != null && curr.next != null; i++) // 拆分出长度为subLen的链表1
                    curr = curr.next;

                // 3.2 拆分subLen长度的链表2
                ListNode head_2 = curr.next; // 第二个链表的头 即 链表1尾部的下一个位置
                curr.next = null; // 断开第一个链表和第二个链表的链接
                curr = head_2; // 第二个链表头 重新赋值给curr
                for (int i = 1; i < subLen && curr != null && curr.next != null; i++) // 再拆分出长度为subLen的链表2
                    curr = curr.next;

                // 3.3 再次断开 第二个链表最后的next的链接
                ListNode next = null;
                if (curr != null) {
                    next = curr.next; // next用于记录 拆分完两个链表的结束位置
                    curr.next = null; // 断开链接
                }

                // 3.4 合并两个subLen长度的有序链表
                ListNode merged = merge(head_1, head_2);
                prev.next = merged; // prev.next 指向排好序链表的头
                while (prev.next != null) // while循环 将prev移动到 subLen*2 的位置后去
                    prev = prev.next;

                curr = next; // next用于记录 拆分完两个链表的结束位置
            }
        }
        // 返回新排好序的链表
        return dummyHead.next;
    }

    // 合并两个有序链表（见方法一）
    // public ListNode merge(ListNode l1, ListNode l2)

    // 方法三：自己写的lowb堆排（和快排一样，空间复杂度都是O(n)）-时间复杂度：O(nlogn)，空间复杂度：O(n)
    public ListNode sortList3(ListNode head) {
        PriorityQueue<ListNode> pq = new PriorityQueue<>((node1, node2) -> node1.val - node2.val);// 小根堆
        while (head != null) {// 所有节点入队
            pq.offer(head);
            head = head.next;
        }
        ListNode dummyHead = new ListNode(-1);
        ListNode tail = dummyHead;
        while (!pq.isEmpty()) {
            ListNode cur = pq.poll();
            tail.next = cur;
            tail = cur;
        }
        tail.next = null;
        return dummyHead.next;
    }

    // 方法四：（自己写的）快排 api-时间复杂度：O(nlogn)，空间复杂度：O(n)
    public ListNode sortList4(ListNode head) {
        if (head == null)
            return null;

        List<ListNode> list = new ArrayList<>();
        while (head != null) {
            list.add(head);
            head = head.next;
        }
        int n = list.size();
        Collections.sort(list, (node1, node2) -> node1.val - node2.val);
        for (int i = 0; i < n - 1; i++)
            list.get(i).next = list.get(i + 1);

        list.get(n - 1).next = null;
        return list.get(0);
    }

    // 155. 最小栈
    // 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
    // 实现 MinStack 类:
    // MinStack() 初始化堆栈对象。
    // void push(int val) 将元素val推入堆栈。
    // void pop() 删除堆栈顶部的元素。
    // int top() 获取堆栈顶部的元素。
    // int getMin() 获取堆栈中的最小元素。
    // 提示：
    // -231 <= val <= 231 - 1
    // pop、top 和 getMin 操作总是在 非空栈 上调用
    // push, pop, top, and getMin最多被调用 3 * 104 次

    // 方法一：辅助栈-时间复杂度：O(n)，空间复杂度：O(n)
    class MinStack {
        Deque<Integer> stk;
        Deque<Integer> minstk;

        public MinStack() {
            stk = new ArrayDeque<>();
            minstk = new ArrayDeque<>();
        }

        public void push(int val) {
            if (stk.isEmpty()) {
                stk.push(val);
                minstk.push(val);
            } else {
                stk.push(val);
                minstk.push(Math.min(minstk.peek(), val));
            }
        }

        public void pop() {
            stk.pop();
            minstk.pop();
        }

        public int top() {
            return stk.peek();
        }

        public int getMin() {
            return minstk.peek();
        }
    }

    // 160. 相交链表
    // 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
    // 图示两个链表在节点 c1 开始相交：
    // 题目数据 保证 整个链式结构中不存在环。
    // 注意，函数返回结果后，链表必须保持其原始结构 。
    // 自定义评测：
    // 评测系统 的输入如下（你设计的程序 不适用 此输入）：
    // intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
    // listA - 第一个链表
    // listB - 第二个链表
    // skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
    // skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数
    // 评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。
    // 如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。
    // 提示：
    // listA 中节点数目为 m
    // listB 中节点数目为 n
    // 0 <= m, n <= 3 * 104
    // 1 <= Node.val <= 105
    // 0 <= skipA <= m
    // 0 <= skipB <= n
    // 如果 listA 和 listB 没有交点，intersectVal 为 0
    // 如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]
    // 进阶：你能否设计一个时间复杂度 O(n) 、仅用 O(1) 内存的解决方案？

    // 方法一：哈希集合-时间复杂度：O(m+n)，空间复杂度：O(m)
    // 判断两个链表是否相交，可以使用哈希集合存储链表节点。
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> visited = new HashSet<ListNode>();
        ListNode temp = headA;
        // 首先遍历链表 headA，并将链表 headA 中的每个节点加入哈希集合中。
        while (temp != null) {
            visited.add(temp);
            temp = temp.next;
        }
        temp = headB;
        // 然后遍历链表 headB，对于遍历到的每个节点，判断该节点是否在哈希集合中
        while (temp != null) {
            if (visited.contains(temp))
                return temp;

            temp = temp.next;
        }
        return null;
    }

    // 方法二：双指针-时间复杂度：O(m+n)，空间复杂度：O(1)
    // 精髓在于不相交链表可以看做同时指向null，因此不用做特殊判断
    // 链表 headA 和 headB 的长度分别是 m 和 n。
    // 假设链表 headA 的不相交部分有 a 个节点，链表 headB 的不相交部分有 b 个节点，两个链表相交的部分有 c 个节点，
    // 则有 a+c=m，b+c=n。
    // 如果 a=b，则两个指针会同时到达两个链表相交的节点，此时返回相交的节点；
    // 如果 a!=b，则指针 pA 会遍历完链表 headA，指针 pB 会遍历完链表 headB，两个指针不会同时到达链表的尾节点，
    // 然后指针 pA 移到链表 headB 的头节点，指针 pB 移到链表 headA 的头节点，然后两个指针继续移动，
    // 在指针 pA 移动了 a+c+b 次、指针 pB 移动了b+c+a 次之后，两个指针会同时到达两个链表相交的节点，
    // 该节点也是两个指针第一次同时指向的节点，此时返回相交的节点。
    // 如果两链表不相交，则两指针最后会同时指向null，返回null表示不相交
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        // 一定不相交
        if (headA == null || headB == null)
            return null;

        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }

    // 169. 多数元素
    // 给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
    // 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
    // 进阶：
    // 尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

    // 方法一：哈希表-时间复杂度：O(n)，空间复杂度：O(n)

    // 方法二：排序（下标为 ⌊ n/2 ⌋ 的元素一定是众数）-时间复杂度：O(nlogn)，空间复杂度：O(logn)
    // 如果使用语言自带的排序算法，需要使用 O(logn) 的栈空间。
    // 如果自己编写堆排序，则只需要使用 O(1) 的额外空间。

    // 方法三：随机化-时间复杂度为 O(n)，空间复杂度：O(1)
    // 随机挑选一个下标，检查它是否是众数，如果是就返回，否则继续随机挑选。
    private int randRange(Random rand, int min, int max) {
        return rand.nextInt(max - min) + min;
    }

    private int countOccurences(int[] nums, int num) {
        int count = 0;
        for (int i = 0; i < nums.length; i++)
            if (nums[i] == num)
                count++;

        return count;
    }

    public int majorityElement3(int[] nums) {
        Random rand = new Random();
        int majorityCount = nums.length / 2;// 多数元素至少出现的次数

        while (true) {
            int candidate = nums[randRange(rand, 0, nums.length)];// 随机取一个数
            if (countOccurences(nums, candidate) > majorityCount) // 验证该数出现的次数
                return candidate;
        }
    }

    // 方法四：分治-时间复杂度：O(nlogn)，空间复杂度：O(logn)
    // 使用经典的分治算法递归求解，直到所有的子问题都是长度为 1 的数组。
    // 长度为 1 的子数组中唯一的数显然是众数，直接返回即可。
    // 如果回溯后某区间的长度大于 1，我们必须将左右子区间的值合并。
    // 如果它们的众数相同，那么显然这一段区间的众数是它们相同的值。
    // 否则，我们需要比较两个众数在整个区间内出现的次数来决定该区间的众数。
    private int countInRange(int[] nums, int num, int lo, int hi) {
        int count = 0;
        for (int i = lo; i <= hi; i++)
            if (nums[i] == num)
                count++;

        return count;
    }

    private int majorityElementRec(int[] nums, int lo, int hi) {
        // 长度为 1 的子数组中唯一的数显然是众数，直接返回即可。
        if (lo == hi)
            return nums[lo];

        // 将区间一分为二
        int mid = (hi + lo) / 2;
        int left = majorityElementRec(nums, lo, mid);
        int right = majorityElementRec(nums, mid + 1, hi);

        // 左右子数组众数一致
        if (left == right)
            return left;

        // 左右子数组众数不一致，返回更多者
        int leftCount = countInRange(nums, left, lo, hi);
        int rightCount = countInRange(nums, right, lo, hi);

        return leftCount > rightCount ? left : right;
    }

    public int majorityElement4(int[] nums) {
        return majorityElementRec(nums, 0, nums.length - 1);
    }

    // 方法五：Boyer-Moore 摩尔投票算法-时间复杂度为 O(n)，空间复杂度：O(1)
    // 如果我们把众数记为 +1，把其他数记为 −1，将它们全部加起来，显然和大于 0，从结果本身我们可以看出众数比其他数多。
    // 我们维护一个候选众数 candidate 和它出现的次数 count。初始时 candidate 可以为任意值，count 为 0；
    // 我们遍历数组 nums 中的所有元素，对于每个元素 x，在判断 x 之前，如果 count 的值为 0，我们先将 x 的值赋予 candidate，
    // 随后我们判断 x：
    // 如果 x 与 candidate 相等，那么计数器 count 的值增加 1；
    // 如果 x 与 candidate 不等，那么计数器 count 的值减少 1。
    // 在遍历完成后，candidate 即为整个数组的众数。
    public int majorityElement5(int[] nums) {
        int count = 0;
        int candidate = -1;

        for (int num : nums) {
            if (count == 0)
                candidate = num;

            count += (num == candidate) ? 1 : -1;
        }

        return candidate;
    }

    // 206. 反转链表
    // 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
    // 提示：
    // 链表中节点的数目范围是 [0, 5000]
    // -5000 <= Node.val <= 5000
    // 进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

    // 方法一：迭代-时间复杂度：O(n)，空间复杂度：O(1)
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {// 由curr跳出，需要避免next空指针
            ListNode next = curr.next;// 可看做临时节点，存放curr.next
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

    // 方法二：递归-时间复杂度：O(n)，空间复杂度：O(n)
    public ListNode reverseList2(ListNode head) {
        if (head == null || head.next == null)// 尾节点开始返回
            return head;
        // ListNode nextNode = head.next; 减少额外的空间开销
        ListNode newHead = reverseList2(head.next);
        head.next.next = head;// 下一个节点的next指向当前节点

        // 当前节点指向null 后续会被更改，直到重新回到原头节点，防止新链表末尾（原链表头）成环
        head.next = null;
        return newHead;
    }

    // 215. 数组中的第K个最大元素
    // 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
    // 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
    // 提示：
    // 1 <= k <= nums.length <= 104
    // -104 <= nums[i] <= 104

    // 方法一：基于快速排序的选择方法-时间复杂度：O(n)，空间复杂度：O(logn)
    // 可以用快速排序来解决这个问题，先对原数组排序，再返回倒数第 k 个位置，这样平均时间复杂度是 O(nlogn)，但其实我们可以做的更快。
    // 改进快速排序算法来解决这个问题：
    // 在分解的过程当中，我们会对子数组进行划分，如果划分得到的 q 正好就是我们需要的下标，就直接返回 a[q]；
    // 否则，如果 q 比目标下标小，就递归右子区间，否则递归左子区间。
    // 这样就可以把原来递归两个区间变成只递归一个区间，提高了时间效率。这就是「快速选择」算法。

    // 引入随机化来加速这个过程，它的时间代价的期望是 O(n)
    public int findKthLargest(int[] nums, int k) {
        quickSort(nums, k - 1, 0, nums.length - 1);// 第k大转换为相应下标
        return nums[k - 1];
    }

    private void quickSort(int[] nums, int index, int left, int right) {
        int pivotIndex = partition(nums, left, right);
        if (pivotIndex == index) // pivot最终位置的下标就是要找的
            return;

        if (pivotIndex < index) // 根据结果只选择一边继续查找
            quickSort(nums, index, pivotIndex + 1, right);
        else
            quickSort(nums, index, left, pivotIndex - 1);

    }

    private int partition(int[] nums, int left, int right) {
        Random random = new Random();
        int pivotIndex = random.nextInt(right - left + 1) + left;// 在区间left right之间随机选择一个pivot
        int pivot = nums[pivotIndex];
        swap(nums, pivotIndex, right);// pivot放到最右边去当哨兵
        int index = left;// 交换位
        for (int i = left; i < right; i++) // 索引right上是pivot
            if (nums[i] > pivot) {// 大于pivot的数放在交换位上，即大于pivot的数在左边，降序排列，同理升序（小的放左边）
                swap(nums, i, index);
                index++;// 交换位右移一位
            }

        swap(nums, index, right);// pivot放到最终位置上
        return index;

    }

    private void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }

    // 方法二：基于堆排序的选择方法（不借助优先队列API）-时间复杂度：O(nlogn)，空间复杂度：O(n)
    // 索引的处理像个猪比，看（自己写的）
    // 也可以使用堆排序来解决这个问题——建立一个大根堆（数组映射到树），做 k - 1 次删除操作后堆顶元素就是我们要找的答案。
    int[] myNums;

    public int findKthLargest2(int[] nums, int k) {
        myNums = nums;
        int heapSize = nums.length;
        buildMaxHeap(heapSize);// 建立大根堆
        for (int i = nums.length - 1; i >= nums.length - k + 1; --i) {// i始终指向末尾叶子节点
            swap(0, i);// 交换最大值与末尾叶子节点
            --heapSize;// 等价于删除最大值
            maxHeapify(0, heapSize);// 在指定范围内，将以i为根的子树调整为大根堆
        }
        return nums[0];
    }

    // 建立大根堆
    public void buildMaxHeap(int heapSize) {
        // 对于所有分支节点（节点数向下取整，非叶子节点），从后往前依次调整
        // 不能从前往后，要先处理底层，使可能沉底的最大元素逐层上浮直至最顶
        for (int i = heapSize / 2; i >= 0; --i)
            maxHeapify(i, heapSize);
    }

    // 在指定范围内，将以i为根的子树调整为大根堆（小元素下沉）
    public void maxHeapify(int root, int heapSize) {
        int l = root * 2 + 1, r = root * 2 + 2;// root节点的左右孩子
        int largest = root;
        if (l < heapSize && myNums[l] > myNums[largest])// 左孩子处于范围内且左孩子更大
            largest = l;

        if (r < heapSize && myNums[r] > myNums[largest])// 右孩子处于范围内且右孩子最大
            largest = r;

        if (largest != root) {// root不是最大的
            swap(root, largest);// 交换与最大节点
            maxHeapify(largest, heapSize);// 递归调整
        }
    }

    public void swap(int i, int j) {
        int temp = myNums[i];
        myNums[i] = myNums[j];
        myNums[j] = temp;
    }

    // 方法二：（自己写的）实现大根堆-时间复杂度：O(nlogn)，空间复杂度：O(n)
    // 不在原地建堆，而是复制到新的数组中建堆，下标1开始，方便计算完全二叉树的节点编号
    int[] heap;
    int size;

    // int n;
    public int findKthLargest22(int[] nums, int k) {
        n = nums.length;
        // 1 <= k <= nums.length <= 104 初值为0，不影响堆
        // 填充节点，简化最后一个非叶子节点的操作
        heap = new int[n + 2];
        for (int i = 0; i < n; i++) {
            heap[i + 1] = nums[i];
            size++;
        }

        for (int i = size / 2; i >= 1; i--) // 注意顺序！一定是非叶子节点，从后往前！
            buildHeap(i);

        for (int i = 1; i <= k - 1; i++) {// 出堆k-1个元素，此时堆顶即第k大的元素
            // 最后一个节点放到堆顶，并做下沉操作
            heap[1] = heap[size];
            size--;
            buildHeap(1);
        }
        return heap[1];
    }

    private void buildHeap(int rootIndex) {
        if (rootIndex > size / 2)// 不操作叶子节点
            return;
        int leftIndex = rootIndex * 2;
        int rightIndex = rootIndex * 2 + 1;

        int root = heap[rootIndex];
        int left = heap[leftIndex];
        int right = heap[rightIndex];

        if (root >= left && root >= right)// 已满足堆的性质，无需操作
            return;

        if (left >= right) {
            swap(leftIndex, rootIndex);
            buildHeap(leftIndex);
        } else {
            swap(rightIndex, rootIndex);
            buildHeap(rightIndex);
        }
    }

    // private void swap(int i, int j){
    // int temp = heap[i];
    // heap[i] = heap[j];
    // heap[j] = temp;
    // }

    // 方法三：利用javaAPI的做快排Arrays.sort()，堆排PriorityQueue
    // -时间复杂度：O(nlogk)，空间复杂度：O(k)
    public int findKthLargest3(int[] nums, int k) {
        // 长度为k的小根堆
        PriorityQueue<Integer> pq = new PriorityQueue<>(k, (num1, num2) -> num1 - num2);
        for (int num : nums)
            if (pq.size() < k)
                pq.offer(num);
            else {// 优先队列长度为k，更新最小值
                if (num > pq.peek()) {
                    pq.poll();
                    pq.offer(num);
                }
            }

        return pq.peek();
    }

    // 217. 存在重复元素
    // 给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。
    // 提示：
    // 1 <= nums.length <= 105
    // -109 <= nums[i] <= 109

    // 方法一：排序-时间复杂度：O(nlogn)，空间复杂度：O(logn)
    // 在对数字从小到大排序之后，数组的重复元素一定出现在相邻位置中。
    // 因此，我们可以扫描已排序的数组，每次判断相邻的两个元素是否相等，如果相等则说明存在重复的元素。

    // 方法二：哈希表-时间复杂度：O(n)，空间复杂度：O(n)
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<Integer>();
        for (int x : nums) {
            if (!set.add(x))
                return true;
        }
        return false;
    }

    // 230. 二叉搜索树中第K小的元素
    // 给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。
    // 提示：
    // 树中的节点数为 n 。
    // 1 <= k <= n <= 104
    // 0 <= Node.val <= 104
    // 进阶：如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？

    // 方法一：中序遍历（自己写的，dfs）-时间复杂度：O(n)，空间复杂度：O(n)
    class tsolution_230 {
        int index = 0;
        int k;
        int res;
        boolean find = false;

        public int kthSmallest(TreeNode root, int k) {
            this.k = k;
            dfs(root);
            return res;
        }

        private void dfs(TreeNode root) {
            if (root == null || find)
                return;
            dfs(root.left);
            if (++index == k) {
                res = root.val;
                find = true;
            }
            dfs(root.right);
        }
    }

    // 方法一：中序遍历（迭代）-时间复杂度：O(n)，空间复杂度：O(n)
    public int kthSmallest(TreeNode root, int k) {
        Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            --k;
            if (k == 0)
                break;
            root = root.right;
        }
        return root.val;
    }

    // 方法二： 记录子树的结点数-时间复杂度：O(n)，空间复杂度：O(n)
    // 如果你需要频繁地查找第 k 小的值，你将如何优化算法？
    // 在方法一中，我们之所以需要中序遍历前 k 个元素，是因为我们不知道子树的结点数量，不得不通过遍历子树的方式来获知。
    // 因此，我们可以记录下以每个结点为根结点的子树的结点数，并在查找第 k 小的值时，使用如下方法搜索：
    // 令 node 等于根结点，开始搜索。
    // 对当前结点 node 进行如下操作：
    // 如果 node 的左子树的结点数 left 小于 k−1，则第 k 小的元素一定在 node 的右子树中，
    // 令 node 等于其的右子结点，k 等于 k−left−1，并继续搜索；
    // 如果 node 的左子树的结点数 left 等于 k−1，则第 k 小的元素即为 nodenode ，结束搜索并返回 node 即可；
    // 如果 node 的左子树的结点数 left 大于 k−1，则第 k 小的元素一定在 node 的左子树中，令 node 等于其左子结点，并继续搜索。
    class tsolution_230_2 {
        class MyBst {
            TreeNode root;
            Map<TreeNode, Integer> nodeNum;

            public MyBst(TreeNode root) {
                this.root = root;
                this.nodeNum = new HashMap<TreeNode, Integer>();
                countNodeNum(root);
            }

            // 返回二叉搜索树中第k小的元素
            public int kthSmallest(int k) {
                TreeNode node = root;
                while (node != null) {
                    int left = getNodeNum(node.left);
                    if (left < k - 1) {
                        node = node.right;
                        k -= left + 1;
                    } else if (left == k - 1)
                        break;
                    else
                        node = node.left;

                }
                return node.val;
            }

            // 统计以node为根结点的子树的结点数
            private int countNodeNum(TreeNode node) {
                if (node == null)
                    return 0;

                nodeNum.put(node, 1 + countNodeNum(node.left) + countNodeNum(node.right));
                return nodeNum.get(node);
            }

            // 获取以node为根结点的子树的结点数
            private int getNodeNum(TreeNode node) {
                return nodeNum.getOrDefault(node, 0);
            }
        }

        public int kthSmallest(TreeNode root, int k) {
            MyBst bst = new MyBst(root);
            return bst.kthSmallest(k);
        }
    }

    // 方法三：平衡二叉搜索树-时间复杂度：预处理的时间复杂度为 O(N)，其中 N 是树中结点的总数。
    // 插入、删除和搜索的时间复杂度均为 O(logN)。
    // 空间复杂度：O(N)

    // 如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？
    // 预备知识
    // 方法三需要先掌握 平衡二叉搜索树（AVL树） 的知识。平衡二叉搜索树具有如下性质：
    // 平衡二叉搜索树中每个结点的左子树和右子树的高度最多相差 1；
    // 平衡二叉搜索树的子树也是平衡二叉搜索树；
    // 一棵存有 n 个结点的平衡二叉搜索树的高度是 O(logn)。
    class tsolution_230_3 {
        public int kthSmallest(TreeNode root, int k) {
            // 中序遍历生成数值列表
            List<Integer> inorderList = new ArrayList<Integer>();
            inorder(root, inorderList);

            // 构造平衡二叉搜索树
            AVL avl = new AVL(inorderList);

            // 模拟1000次插入和删除操作
            int[] randomNums = new int[1000];
            Random random = new Random();
            for (int i = 0; i < 1000; ++i) {
                randomNums[i] = random.nextInt(10001);
                avl.insert(randomNums[i]);
            }
            shuffle(randomNums); // 列表乱序
            for (int i = 0; i < 1000; ++i)
                avl.delete(randomNums[i]);

            return avl.kthSmallest(k);
        }

        private void inorder(TreeNode node, List<Integer> inorderList) {
            if (node.left != null)
                inorder(node.left, inorderList);

            inorderList.add(node.val);
            if (node.right != null)
                inorder(node.right, inorderList);
        }

        private void shuffle(int[] arr) {
            Random random = new Random();
            int length = arr.length;
            for (int i = 0; i < length; i++) {
                int randIndex = random.nextInt(length);
                int temp = arr[i];
                arr[i] = arr[randIndex];
                arr[randIndex] = temp;
            }
        }

        // 平衡二叉搜索树（AVL树）：允许重复值
        class AVL {
            Node root;

            // 平衡二叉搜索树结点
            class Node {
                int val;
                Node parent;
                Node left;
                Node right;
                int size;
                int height;

                public Node(int val) {
                    this(val, null);
                }

                public Node(int val, Node parent) {
                    this(val, parent, null, null);
                }

                public Node(int val, Node parent, Node left, Node right) {
                    this.val = val;
                    this.parent = parent;
                    this.left = left;
                    this.right = right;
                    this.height = 0; // 结点高度：以node为根节点的子树的高度（高度定义：叶结点的高度是0）
                    this.size = 1; // 结点元素数：以node为根节点的子树的节点总数
                }
            }

            public AVL(List<Integer> vals) {
                if (vals != null) {
                    this.root = build(vals, 0, vals.size() - 1, null);
                }
            }

            // 根据vals[l:r]构造平衡二叉搜索树 -> 返回根结点
            private Node build(List<Integer> vals, int l, int r, Node parent) {
                int m = (l + r) >> 1;
                Node node = new Node(vals.get(m), parent);
                if (l <= m - 1) {
                    node.left = build(vals, l, m - 1, node);
                }
                if (m + 1 <= r) {
                    node.right = build(vals, m + 1, r, node);
                }
                recompute(node);
                return node;
            }

            // 返回二叉搜索树中第k小的元素
            public int kthSmallest(int k) {
                Node node = root;
                while (node != null) {
                    int left = getSize(node.left);
                    if (left < k - 1) {
                        node = node.right;
                        k -= left + 1;
                    } else if (left == k - 1) {
                        break;
                    } else {
                        node = node.left;
                    }
                }
                return node.val;
            }

            public void insert(int v) {
                if (root == null) 
                    root = new Node(v);
                 else {
                    // 计算新结点的添加位置
                    Node node = subtreeSearch(root, v);
                    boolean isAddLeft = v <= node.val; // 是否将新结点添加到node的左子结点
                    if (node.val == v) { // 如果值为v的结点已存在
                        if (node.left != null) { // 值为v的结点存在左子结点，则添加到其左子树的最右侧
                            node = subtreeLast(node.left);
                            isAddLeft = false;
                        } else  // 值为v的结点不存在左子结点，则添加到其左子结点
                            isAddLeft = true;
                        
                    }

                    // 添加新结点
                    Node leaf = new Node(v, node);
                    if (isAddLeft) 
                        node.left = leaf;
                     else 
                        node.right = leaf;
                    

                    rebalance(leaf);
                }
            }

            // 删除值为v的结点 -> 返回是否成功删除结点
            public boolean delete(int v) {
                if (root == null) 
                    return false;
                

                Node node = subtreeSearch(root, v);
                if (node.val != v) // 没有找到需要删除的结点
                    return false;
                

                // 处理当前结点既有左子树也有右子树的情况
                // 若左子树比右子树高度低，则将当前结点替换为右子树最左侧的结点，并移除右子树最左侧的结点
                // 若右子树比左子树高度低，则将当前结点替换为左子树最右侧的结点，并移除左子树最右侧的结点
                if (node.left != null && node.right != null) {
                    Node replacement = null;
                    if (node.left.height <= node.right.height) 
                        replacement = subtreeFirst(node.right);
                     else 
                        replacement = subtreeLast(node.left);
                    
                    node.val = replacement.val;
                    node = replacement;
                }

                Node parent = node.parent;
                delete(node);
                rebalance(parent);
                return true;
            }

            // 删除结点p并用它的子结点代替它，结点p至多只能有1个子结点
            private void delete(Node node) {
                if (node.left != null && node.right != null) {
                    return;
                    // throw new Exception("Node has two children");
                }
                Node child = node.left != null ? node.left : node.right;
                if (child != null) 
                    child.parent = node.parent;
                
                if (node == root) 
                    root = child;
                else {
                    Node parent = node.parent;
                    if (node == parent.left) 
                        parent.left = child;
                     else 
                        parent.right = child;
                    
                }
                node.parent = node;
            }

            // 在以node为根结点的子树中搜索值为v的结点，如果没有值为v的结点，则返回值为v的结点应该在的位置的父结点
            private Node subtreeSearch(Node node, int v) {
                if (node.val < v && node.right != null) 
                    return subtreeSearch(node.right, v);
                else if (node.val > v && node.left != null) 
                    return subtreeSearch(node.left, v);
                 else 
                    return node;
                
            }

            // 重新计算node结点的高度和元素数
            private void recompute(Node node) {
                node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));
                node.size = 1 + getSize(node.left) + getSize(node.right);
            }

            // 从node结点开始（含node结点）逐个向上重新平衡二叉树，并更新结点高度和元素数
            private void rebalance(Node node) {
                while (node != null) {
                    int oldHeight = node.height, oldSize = node.size;
                    if (!isBalanced(node)) {
                        node = restructure(tallGrandchild(node));
                        recompute(node.left);
                        recompute(node.right);
                    }
                    recompute(node);
                    if (node.height == oldHeight && node.size == oldSize) 
                        node = null; // 如果结点高度和元素数都没有变化则不需要再继续向上调整
                     else 
                        node = node.parent;
                    
                }
            }

            // 判断node结点是否平衡
            private boolean isBalanced(Node node) {
                return Math.abs(getHeight(node.left) - getHeight(node.right)) <= 1;
            }

            // 获取node结点更高的子树
            private Node tallChild(Node node) {
                if (getHeight(node.left) > getHeight(node.right)) 
                    return node.left;
                 else 
                    return node.right;
                
            }

            // 获取node结点更高的子树中的更高的子树
            private Node tallGrandchild(Node node) {
                Node child = tallChild(node);
                return tallChild(child);
            }

            // 重新连接父结点和子结点（子结点允许为空）
            private static void relink(Node parent, Node child, boolean isLeft) {
                if (isLeft) 
                    parent.left = child;
                else 
                    parent.right = child;
                
                if (child != null) 
                    child.parent = parent;
                
            }

            // 旋转操作
            private void rotate(Node node) {
                Node parent = node.parent;
                Node grandparent = parent.parent;
                if (grandparent == null) {
                    root = node;
                    node.parent = null;
                } else 
                    relink(grandparent, node, parent == grandparent.left);
                

                if (node == parent.left) {
                    relink(parent, node.right, true);
                    relink(node, parent, false);
                } else {
                    relink(parent, node.left, false);
                    relink(node, parent, true);
                }
            }

            // trinode操作
            private Node restructure(Node node) {
                Node parent = node.parent;
                Node grandparent = parent.parent;

                if ((node == parent.right) == (parent == grandparent.right)) { // 处理需要一次旋转的情况
                    rotate(parent);
                    return parent;
                } else { // 处理需要两次旋转的情况：第1次旋转后即成为需要一次旋转的情况
                    rotate(node);
                    rotate(node);
                    return node;
                }
            }

            // 返回以node为根结点的子树的第1个元素
            private static Node subtreeFirst(Node node) {
                while (node.left != null) 
                    node = node.left;
                
                return node;
            }

            // 返回以node为根结点的子树的最后1个元素
            private static Node subtreeLast(Node node) {
                while (node.right != null) 
                    node = node.right;
                
                return node;
            }

            // 获取以node为根结点的子树的高度
            private static int getHeight(Node node) {
                return node != null ? node.height : 0;
            }

            // 获取以node为根结点的子树的结点数
            private static int getSize(Node node) {
                return node != null ? node.size : 0;
            }
        }
    }

    // 231. 2的幂
    // 给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。
    // 如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。
    // 提示：
    // -231 <= n <= 231 - 1

    // 方法一：二进制表示（Brian Kernighan 算法）
    public boolean isPowerOfTwo(int n) {
        return n > 0 && (n & (n - 1)) == 0;
    }

    // 方法一：二进制表示（另一种位运算技巧）
    public boolean isPowerOfTwo1(int n) {
        return n > 0 && (n & -n) == n;
    }

    // 方法一：（自己写的）位运算
    public boolean isPowerOfTwo11(int n) {
        if (n < 0)
            return false;
        int ones = 0;
        while (n != 0) {
            if ((n & 1) == 1)
                ones++;
            if (ones > 1)
                return false;
            n = n >> 1;
        }
        return ones == 1;
    }

    // 方法一：（自己写的）java api
    public boolean isPowerOfTwo111(int n) {
        if (n < 0)
            return false;
        return Integer.bitCount(n) == 1;
    }

    // 方法二：判断是否为最大 2 的幂的约数
    // 除了使用二进制表示判断之外，还有一种较为取巧的做法。
    // 在题目给定的 32 位有符号整数的范围内，最大的 2 的幂为 2^30 = 1073741824。我们只需要判断 n 是否是 2^30 的约数即可。
    static final int BIG = 1 << 30;

    public boolean isPowerOfTwo2(int n) {
        return n > 0 && BIG % n == 0;
    }

    // 235. 二叉搜索树的最近公共祖先
    // 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
    // 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，
    // 满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
    // 说明:
    // 所有节点的值都是唯一的。
    // p、q 为不同节点且均存在于给定的二叉搜索树中。

    // 方法一：两次遍历-时间复杂度：O(n)，空间复杂度：O(n)
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> path_p = getPath(root, p);
        List<TreeNode> path_q = getPath(root, q);
        TreeNode ancestor = null;
        for (int i = 0; i < path_p.size() && i < path_q.size(); ++i) {
            if (path_p.get(i) == path_q.get(i))
                ancestor = path_p.get(i);
            else
                break;
        }
        return ancestor;
    }

    public List<TreeNode> getPath(TreeNode root, TreeNode target) {
        List<TreeNode> path = new ArrayList<TreeNode>();
        TreeNode node = root;
        while (node != target) {
            path.add(node);
            if (target.val < node.val)
                node = node.left;
            else
                node = node.right;
        }
        path.add(node);
        return path;
    }

    // 方法二：一次遍历-时间复杂度：O(n)，空间复杂度：O(1)
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode ancestor = root;
        while (true) {
            if (p.val < ancestor.val && q.val < ancestor.val)
                ancestor = ancestor.left;
            else if (p.val > ancestor.val && q.val > ancestor.val)
                ancestor = ancestor.right;
            else
                break;
        }
        return ancestor;
    }

    // 236. 二叉树的最近公共祖先
    // 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先
    // 公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x
    // 满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）
    // 树中节点数目在范围 [2, 105] 内
    // -109 <= Node.val <= 109
    // 所有 Node.val 「互不相同」
    // p != q
    // p 和 q 均存在于给定的二叉树中

    // 方法一：递归DFS（后序遍历）-时间复杂度，空间复杂度-O(n)
    // 递归遍历整棵二叉树，定义 fx 表示 x 节点的子树中是否包含 p 节点或 q 节点，如果包含为 true，否则为 false
    // 那么符合条件的最近公共祖先 x 一定满足如下条件：
    // (flson && frson) ||  ((x = p || x = q) && (flson || frson))
    // flson && frson一定符合
    // (x = p || x = q) && (flson || frson)同时满足也符合，即父节点是p或q且另一个在其左或右子树下
    class tsolution_236 {
        TreeNode ans = null;

        boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
            if (root == null)
                return false;
            boolean lson = dfs(root.left, p, q);// p q 是否在左子树下
            boolean rson = dfs(root.right, p, q);// p q 是否在右子树下
            if ((lson && rson) || ((root.val == p.val || root.val == q.val) && (lson || rson)))
                ans = root;

            return lson || rson || (root.val == p.val || root.val == q.val);// p q是否在该节点下，或该节点就是p q
        }

        TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            this.dfs(root, p, q);
            return ans;
        }
    }

    // 方法二：存储父节点-时间复杂度，空间复杂度-O(n)
    // 不是顺序二叉树，不能简单通过序号来判断是否是父节点
    class tsolution_236_2 {
        Map<Integer, TreeNode> parent = new HashMap<Integer, TreeNode>();// 键值对，key为节点val，value为该节点的父节点
        Set<Integer> visited = new HashSet<Integer>();// 所有节点p的祖先节点（包括p自身）

        void dfs(TreeNode root) {
            if (root.left != null) {
                parent.put(root.left.val, root);
                dfs(root.left);
            }
            if (root.right != null) {
                parent.put(root.right.val, root);
                dfs(root.right);
            }
        }

        TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            dfs(root);
            while (p != null) {
                visited.add(p.val);// p的所有父节点，包括p节点自己
                p = parent.get(p.val);// p的父节点
            }
            while (q != null) {
                if (visited.contains(q.val))// 找到共同的祖先节点
                    return q;
                q = parent.get(q.val);
            }
            return null;
        }
    }
    
    // 237. 删除链表中的节点
    // 有一个单链表的 head，我们想删除它其中的一个节点 node。
    // 给你一个需要删除的节点 node 。你将 无法访问 第一个节点  head。
    // 链表的所有值都是 唯一的，并且保证给定的节点 node 不是链表中的最后一个节点。
    // 删除给定的节点。注意，删除节点并不是指从内存中删除它。这里的意思是：
    // 给定节点的值不应该存在于链表中。
    // 链表中的节点数应该减少 1。
    // node 前面的所有值顺序相同。
    // node 后面的所有值顺序相同。
    // 提示：
    // 链表中节点的数目范围是 [2, 1000]
    // -1000 <= Node.val <= 1000
    // 链表中每个节点的值都是 唯一 的
    // 需要删除的节点 node 是 链表中的节点 ，且 不是末尾节点

    // 方法一：和下一个节点交换
    // 无法删除末尾节点（提示中也有避开末尾节点）
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }

    // 238. 除自身以外数组的乘积
    // 给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，
    // 其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
    // 提示：题目数据保证数组之中任意元素的全部前缀元素和后缀（甚至是整个数组）的乘积都在 32 位整数范围内。
    // 说明: 请「不要使用除法」，且在 O(n) 时间复杂度内完成此题。
    // 进阶：
    // 你可以在常数空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）

    // 方法一：左右乘积列表-时间复杂度：O(n)，空间复杂度：O(n)
    // 数组 L 和 R。对于给定索引 i，L[i] 代表的是 i 左侧所有数字的乘积，R[i] 代表的是 i 右侧所有数字的乘积。
    public int[] productExceptSelf(int[] nums) {
        int length = nums.length;

        // L 和 R 分别表示左右两侧的乘积列表
        int[] L = new int[length];
        int[] R = new int[length];
        int[] answer = new int[length];

        // L[i] 为索引 i 左侧所有元素的乘积
        // 对于索引为 '0' 的元素，因为左侧没有元素，所以 L[0] = 1
        L[0] = 1;
        for (int i = 1; i < length; i++)
            L[i] = nums[i - 1] * L[i - 1];

        // R[i] 为索引 i 右侧所有元素的乘积
        // 对于索引为 'length-1' 的元素，因为右侧没有元素，所以 R[length-1] = 1
        R[length - 1] = 1;
        for (int i = length - 2; i >= 0; i--)
            R[i] = nums[i + 1] * R[i + 1];

        // 对于索引 i，除 nums[i] 之外其余各元素的乘积就是左侧所有元素的乘积乘以右侧所有元素的乘积
        for (int i = 0; i < length; i++)
            answer[i] = L[i] * R[i];

        return answer;
    }

    // 方法二：找规律-时间复杂度：O(n)，空间复杂度：O(1)
    // 先把输出数组当作 L 数组来计算，然后再动态构造 R 数组得到结果
    public int[] productExceptSelf2(int[] nums) {
        int length = nums.length;
        int[] answer = new int[length];

        // answer[i] 表示索引 i 左侧所有元素的乘积
        // 因为索引为 '0' 的元素左侧没有元素， 所以 answer[0] = 1
        answer[0] = 1;
        for (int i = 1; i < length; i++)
            answer[i] = nums[i - 1] * answer[i - 1];

        // R 为右侧所有元素的乘积
        // 刚开始右边没有元素，所以 R = 1
        int R = 1;
        for (int i = length - 1; i >= 0; i--) {
            // 对于索引 i，左边的乘积为 answer[i]，右边的乘积为 R
            answer[i] = answer[i] * R;
            // R 需要包含右边所有的乘积，所以计算下一个结果时需要将当前值乘到 R 上
            R *= nums[i];
        }
        return answer;
    }

    // 方法二：（自己写的）找规律-时间复杂度：O(n)，空间复杂度：O(1)
    public int[] productExceptSelf22(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        Arrays.fill(res, 1);

        int leftProduct = 1;
        for (int i = 1; i < n; i++) {
            leftProduct *= nums[i - 1];
            res[i] *= leftProduct;
        }

        int rightProduct = 1;
        for (int i = n - 2; i >= 0; i--) {
            rightProduct *= nums[i + 1];
            res[i] *= rightProduct;
        }

        return res;
    }

    // 292. Nim游戏
    // 你和你的朋友，两个人一起玩 Nim 游戏：
    // 桌子上有一堆石头。
    // 你们轮流进行自己的回合， 你作为先手 。
    // 每一回合，轮到的人拿掉 1 - 3 块石头。
    // 拿掉最后一块石头的人就是获胜者。
    // 假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。
    // 如果可以赢，返回 true；否则，返回 false 。
    // 提示：
    // 1 <= n <= 231 - 1

    // 方法一：数学推理-时间复杂度：O(1)，空间复杂度：O(1)
    public boolean canWinNim(int n) {
        return n % 4 != 0;
    }

    // 344. 反转字符串
    // 编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
    // 不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
    // 提示：
    // 1 <= s.length <= 105
    // s[i] 都是 ASCII 码表中的可打印字符

    // 方法一：双指针-时间复杂度：O(n)，空间复杂度：O(1)
    public void reverseString(char[] s) {
        int n = s.length;
        for (int left = 0, right = n - 1; left < right; ++left, --right) {
            char tmp = s[left];
            s[left] = s[right];
            s[right] = tmp;
        }
    }

    // 方法一：双指针（其实就是交换位置）-时间复杂度：O(n)，空间复杂度：O(1)
    public void reverseString11(char[] s) {
        int n = s.length;
        for (int i = 0; i < n >> 1; i++) {
            char temp = s[i];
            s[i] = s[n - 1 - i];
            s[n - 1 - i] = temp;
        }
    }

    // 557. 反转字符串中的单词II
    // 给定一个字符串 s ，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。
    // 提示：
    // 1 <= s.length <= 5 * 104
    // s 包含可打印的 ASCII 字符。
    // s 不包含任何开头或结尾空格。
    // s 里 至少 有一个词。
    // s 中的所有单词都用一个空格隔开。

    // 方法一：使用额外空间-时间复杂度：O(n)，空间复杂度：O(n)
    // 开辟一个新字符串。然后从头到尾遍历原字符串，直到找到空格为止，此时找到了一个单词，并能得到单词的起止位置。
    // 随后，根据单词的起止位置，可以将该单词逆序放到新字符串当中。
    // 如此循环多次，直到遍历完原字符串，就能得到翻转后的结果。
    public String reverseWords(String s) {
        StringBuffer ret = new StringBuffer();
        int length = s.length();
        int i = 0;
        while (i < length) {
            int start = i;
            while (i < length && s.charAt(i) != ' ')
                i++;

            for (int p = start; p < i; p++)
                ret.append(s.charAt(start + i - 1 - p));

            while (i < length && s.charAt(i) == ' ') {
                i++;
                ret.append(' ');
            }
        }
        return ret.toString();
    }

    // 方法一：（自己写的）使用额外空间-时间复杂度：O(n)，空间复杂度：O(n)
    public String reverseWords11(String s) {
        // 拆分单词
        String[] strs = s.split(" ");

        // 反转单词
        for (int i = 0; i < strs.length; i++) {
            char[] chars = strs[i].toCharArray();
            int n = chars.length;
            for (int j = 0; j < n >> 1; j++) {
                char temp = chars[j];
                chars[j] = chars[n - 1 - j];
                chars[n - 1 - j] = temp;
            }
            strs[i] = new String(chars);
        }

        // 合并单词
        StringBuilder res = new StringBuilder();
        for (String str : strs)
            res.append(str).append(" ");
        res.deleteCharAt(res.length() - 1);
        return res.toString();
    }

    // 方法二：原地解法
    // 思路与算法
    // 此题也可以直接在原字符串上进行操作，避免额外的空间开销。
    // 当找到一个单词的时候，我们交换字符串第一个字符与倒数第一个字符，随后交换第二个字符与倒数第二个字符……
    // 如此反复，就可以在原空间上翻转单词。
    // 需要注意的是，原地解法在某些语言（比如 Java，JavaScript）中不适用，因为在这些语言中 String 类型是一个不可变的类型。
}

public class TencentSelected {

    public static void main(String[] args) {
    }
}